Best to try fixing the issue, before resorting to a full wipe and reinstall...

Firstly, what's the page that you get redirected to, when you try to visit Google? Don't put it in as a link, someone's bound to try and click on it!

Although if you're resolute about formatting and starting again, rebooting with the XP CD in the drive should, if you have the CD-ROM drive set as first boot-device (in your BIOS settings), fire off the reinstallation-process (it asks during it, if you want to format the drive).