I run into something like this occasionally and it is because my email domain has ended up on some spam blacklist somewhere. It has nothing to do with Drupal.

Nancy

Injustice anywhere is a threat to justice everywhere. -- Dr. Martin L. King, Jr.

From: Afan Pasalic

On my Drupal 6 Contact form page (the simple one, without any additions)
, as Categories I put names and in Recipients field their email address.
As it should be.
A visitor will select the name, enter question and after the visitor
submitted the Contact form, email should arrive to selected person's Inbox.
Though, if I select myself (and email is the one above, the one I use in
this email) I'll get the contact. But if I use FLast@UKexample.co.uk the
email/contact will never reach the destination. The email
FLast@UKexample.co.uk is valid because if I send an email to this email
by Gmail or any other way - it will get there. Looks like Drupal doesn't
accept UK email format (.co.uk) :-)
Any idea how and/or where I can check what's causing the issue?