Your host uses a Belkin router right? That alone should have been enough to suggest they're not capable of being a server host :P
Anyways, the problem has been known to me for some time. I only know one sure fire way around it - and thats to use a piece of software I wrote to get around the problem (the router not supporting half-nat).
The other way that was suggested to me was to use the non-ledu 1.9 client and force connect to the NETWORK IP when used from within the LAN. Now I've no idea what the person meant by non-ledu, but maybe you do.
If the latter suggestion fails, try and catch me on MSN (you'll be very lucky atm) and I'll guide you through it.
/Leo