You said sending emails from Admin->Tools->Send Email works fine, right?
What happens if you create a customer account in the store with the same address that your contact-us is going to, and then test sending an email via the admin to that address?