Can't send e-mail with specific mail domains

Drupal versions: 6.10 and 6.9

Problem:

Mailing system works fine for short domains (myname@drupal.org) but when it comes to strange ones (myname@something.strange.com) it fails.

I've checked it for several different adresses and when mail have more "dots" then one after @ it always fails.