it is always worth testing SMTP using "external" mail server. For example, gmail (http://support.google.com/mail/bin/answer.py?hl=en&answer=13287).
If gmail SMTP sends out emails ok, then the issue is in your mail server's settings.
Are you on a dedicated or shared server?
It shows up there before its sent, then once its sent it will go away.
Also if you want to skip that since you are on a vps you can go to your WHM (for cpanel) and check your server mail outgoing mails, you can do a search by day or date or other kinds of searches and see if the email is listed there.
If it is listed then it was sent and it is up to the client (ie hotmail or whatever) '
If it is not listed then go check the table to see if it shows up..
Also check your error logs ow_log and also look for the normal error log from the system itself in the root dir to see if it has any errors.
How did you determine that your cron job works?
This could have come from the contact page we dont know yet if it was actually from the inside yet, so dont jump the gun just yet. Let us do some investigation first.
Let me look at what you sent me more closely while you secure your server. Make sure you dont have any server emails that are not suppose to be there.
I will get back with you in a moment..