If I understand this correctly, your wired connection is fine and so this is not an ISP problem.
If so, have you tried changing channel on the router? Re-locating the router?
Stripping encryption, i.e. turn off WEP or WPA and see if the connectivity improves.
It is also worth switching on SSID broadcast if you have it turned off.
It could be a duff wireless card/adaptor in one of the PC's. Try it with all but one PC turned off. If it works. Try the next one....
RealVNC is going to give problems whilst you have this wireless problems. The DHCP server in your router will be continuously establishing and reestablishing IP leases.
Sorry I cannot offer much more help at the moment.