Did you alter Deus Ex in any shape or form (I don't mean for installing mods, I meant hardcore value changing, beside the DXMTL1.52's suggested network setting.).
Are you running any other firewall? (Software based, such as ZoneAlarm, Norton, etc..).
If not, you may want to consider a demo trial of a firewall of some sort (Norton offered one for 30 days free, I know that) so you can confirm that Deus Ex indeed "try" to access the Internet to "report" your server being hosted to Gamespy. (< That step is crucial obviously to it being seen at all from the Internet).