The trigger for this problem is your DNS server, or a NAT router which manipulates your DNS requests before they go to the server and return to you. You can try changing your DNS server or updating/removing your cheapy router. If you find success, report the bug to Apple and your cheapy router maker, or your DNS server admin, as required.
The most likely parties to fix this problem are Apple and the cheapy router maker. In fact, since this problem was WORSE before 10.5.2 and/or Security Update 2007-X (i.e., it affected me too, and I don't have a cheapy router!), it is possible the fix was incomplete by Apple.
Re: Firefox. Firefox is a cross-platform app that uses BSD socket API and is going to do so in the most generic and compatible ways. Safari is a proprietary app that is going to use whatever fancy widgets, thingamajiggers, and gizmos that Apple has bolted on to their OS. It is very easy for one to work, and the other to fail at what appears to be the same function. Apple is notorious for having multiple APIs for doing the same thing.