My guess is the setting of cron.php to run every minute has caused a lot of things to stand on top of each other, ie, not finish before the next task scheduled of the same nature or similar is executed. Since both cron.php would not be aware of each state. The same record could be attempted twice causing some odd exception breaking the queue email sends.
With that said there are Mage::Log in the exceptions of the Queue Mailer, so making sure the logging is enabled would be the best step to help determine if theres any exceptions. It may be wise to also just run php -f cron.php from CLI to see if it is also throwing any exceptions, you may not be seeing with it running behind the scenes.
I would also start with a simple PHP mail() test to make sure you're not running into any Spam policies or such. Just to be sure its not something lower in the stack causing the issue.
Just some speculation, hope it helps!
*** EDIT ***
Use cron.sh instead of cron.php as it will do grep ps to look to see if a previous process is already running.