The fact that any emails can send at all is a good sign, but it would be worth checking they are sending as expected. Enable logging (system->config->developer menu) and check the log output after these operations:
- SMTP Pro self test
- manually sending an email via admin
- contact form submission
- placing a new order
1) and 2) should show SMTP related output. If they don't then it means that although SMTP Pro is installed, something else (another extension, code modification) is interfering with email sending.
If 3) and 4) show SMTP Pro output then it's a weird situation where SMTP Pro works for some emails but not all - I'm reasonably confident that won't be the case here - if it is send me more details.
At this stage it'd also be good to check the exception logs in Magento, and the Apache logs to make sure some error is not occurring when you tested 1-4.
At this point you're going to need to step through either the contact form or new order process and see why it's not sending emails - if you have a debugger, use that. Otherwise, get busy with Mage::log() in the Contact Form code - start with the controller Mage_Contacts_IndexController.
As @Roscius pointed out, order emails not sending could be caused by configuration, so I'd suggest focus on contact form first, it's an easier module to debug through.
It's entirely possible it's two different issues though, as there's not a lot of overlap between the contact form sending, and the new order email sending.
If you update your questions with more info from the above debugging steps, it will help diagnose the issue further.