Got a new VPS hosting server with 1&1, its one of their Cloud Virtual Servers based on SSD, nice and speedy. Obscure problem with the first WordPress site which wouldn't send outgoing email using phpmail.
Went through all the firewall policy, server settings, Plesk, OS, WordPress - nothing obvious. All you can see is emails queuing in the outgoing queue in Plesk. Look under Tools & Settings > Mail > Mail Server Settings > Mail Queue.
Clicking on the email shows it received by the host.
After double-checking all the settings, again, turns out its an overriding outgoing port 25 block set by 1and1. You have to phone support and get the outgoing block taken off port 25 - it doesn't appear in the control panel(s) or the firewall policies. Good luck finding a first line tech that's heard of it too :-)