I would've thought that if it was working for internet, it would be ok but I'm no expert! The idea of switching modems was kind of a last resort There's no firewall in yours anyway. Have you been right through control panel & also looked in your system tray for all security programs that might have a firewall?
Have you tried turning off the XP firewall, just for a very short time, since you deleted Norton?

Have you tried installing one of the older versions since you deleted Norton?

I'm stumped. Someone else might have more ideas. If you had a laptop, you could take it to someone else's house (who uses a different ISP) & try to connect.

Sorry...