Try entering in the ISPs NT domain as part of your login (eg. MYDOMAIN\USERNAME ). Maybe the login is default to your local domain (which has no trust relationship with the ISPs) and thus failing.
My other guess would be that NT authentication utilises a port that's closed.
(but that only a very very rough guess)
Regards,
Luke