It is entered via pressing the F8 at bootup and selecting that option from the screen.
315222 - A Description of the Safe Mode Boot Options in Windows XP
Not every bit of Networking will work in "Safe Mode with Networking", it just depends on whether Windows loads drivers that you require, basic Networking (surfing etc.) does work, so it is a sort of an experiment if you like.
On the problem machine, are there any clues coming from the Event Viewer?
Do you see your current faults if you log on in Normal Mode as someone else?
Have you tried the Winsock fix as per this FAQ?
WinXP Connectivity Issues
faq779-4625
310560 - How to Troubleshoot By Using the Msconfig Utility in Windows XP
Some general things to try.
See if System Restore will get you back to a restore point before your problem with VNC.
Try running ChkDsk to check your drive for errors. Right-click your Drive icon/ Properties/ Tools/ Error Checking. Select both boxes.
Run the System File Checker program from the Run Box by typing.....Sfc /Scannow in it and have your XP CD handy.
HOW TO: Verify Unsigned Device Drivers in Windows XP
If they don't work you could try repairing windows by running it over itself. You will lose all your windows updates but your files will be untouched.
How to Perform an In-Place Upgrade (Reinstallation) of Windows XP (Q315341)