I don't think I could make the title any clearer or search engine friendly and I hope no one ever has to lose sleep over this ever again.

I'm sure you've done all the right things:

1. Set up and pair devices using Bluetooth
2. In System Preferences -> Sharing enable Internet Sharing on the Ethernet Port
3. In System Preferences -> Bluetooth -> Advanced check the option to "Share my Internet connection with other Bluetooth devices"
4. Join a Personal Area Network from the context menu on the Bluetooth icon in Windows XP

At this point you're likely to be getting an invalid IP address or automatic private IP address on the Windows XP box. You need to follow some additional steps to get things working right.

1. In a terminal window run the command "sudo ifconfig en2 inet 10.0.0.1 netmask 255.255.255.0
2. Get the IP address of the DNS server used by your mac by going to System Preferences -> Network -> Advanced -> DNS. Use the address that looks like the address of your wired or wireless router. Mine is "192.168.1.254".
3. On the Windows XP box right click the Bluetooth network connection, choose status from the context menu and then click the general tab and click Properties. In the Internet Protocol (TCP/IP) properties, manually configure the IP, Subnet, Gateway and DNS server to be 10.0.0.2, 255.255.255.0, 10.0.0.1 and 192.168.1.254
4. Apply the changes and enjoy using the internet on your Windows XP box via your Mac

If there is a conflict with your other adapters when you use 10.0.0.1 and 10.0.0.2 try another sequence like 10.0.1.1 and 10.0.1.2.

Thats all. Good luck!