If you have updated your Magento site to the latest version 1.9.1 you should note that email handling has been revamped. Emails are now responsive, yay, since at least 50% people read their emails on a mobile device and most importantly all emails* are being sent via CRON job including transactional emails.
So, if you are having troubles with magento emails not being sent to your customers all of a sudden, you just need to set/check up on CRON job on your server to see if it is working properly.
According to this thread contact emails are being sent outside of the queue. We tested it on a clean Magento 1.9.1 installation and can confirm the same.
Read on, we prepared a setup overview and as a bonus a reference to a Magento extension that monitors all CRON jobs.
First of all, every email from now on will be queued, meaning that sending will depend on the set interval. In general, 5 minutes for all emails should suffice, although being used to see emails delivered right away it can be daunting to see them not delivered right away.
Checking CRON jobs are set in Magento
By default, Magento has already set CRON jobs (Mage_Cron) which you can check by looking at your System-> Advanced -> Cron (Scheduled Tasks).
If you need more info on setting this up please refer to "How to setup a CRON job" at the official Magento WIKI page.
Enabling CRON job is set on your server
This one is pretty easy to investigate. Head on to your hosting cPanel and find the "CRON jobs" section. Upon access, confirm that you have a cron job set on your server and if not just create one and set the desired intervals. Note that you should point your server to the cron.php in your magento root using an absolute path:
Setting up Monitoring with AOE Schedueler
Here comes the best part, extension that should be in my opinion included in Magento by default.
Apart from monitoring, you can set jobs to be "run now", disable or enable them or "Schedule now" this gives you a handle on the situation at all times so you don't have plow through the terminal or ask a developer to make it happen.
Here's how a visual overview enables you to monitor all of the emails Magento is handling:
Hope this overview helped you at least figuring out what is the matter with transactional emails not being sent and that you'll find a peace of mind running your store.
Important: If you still have issues with issues with the CRON check this wiki article on setting it up. There are valuable pointers to help you with ammending the issue.