Problems sending new user information via email

I am having problems sending new user information via email. I login as the administration #1 account and 'add user'. I check the 'notify user of account', but the user never receives the email.

I am checking with my local (miltary) network support group and they indicate that they aren't blocking my incoming emails. I also have word into my webhost, a third party, to see if they can reach the military DNS that I am trying to send to.

Any other thoughts or suggestions? I'm really rather stuck at the moment and would appreciate any thoughts you may have.

Regards,
~Stina