Is your modem connected to a network card in your computer? Or a USB port?
If it's connected to a network card, I'd consider removing the drivers for the network card by removing it in Device Manager. When you reboot, you will have to reinstall the drivers, and then, Windows will automatically reinstall networking protocols. If you are lucky, one of these files are what has been messed with, and restoring Networking to it's default state will fix it. Hopefully. Cross your fingers.
So you know, this is a longshot at best, but you seem to be in a desperate position, it's beginning to look like 'reinstall time', and I take it you'd rather find some other way to fix this.
If it's a USB modem, I have no real experience with them, I can't think of anything suitable short of deleting all TCP/IP networking protocols, and reinstalling them from scratch.
Got yourself a real stumper of a problem here, gotta say it, Chef.