Hi guys,
I am having this problem but with Fasthosts in the UK, not on all sites though.
I haven’t bothered asking fasthosts as my confidence has almost completely gone in them.
I have recently set up a new site on media temple gs hosting and set up the exact contact form I was having trouble with (customised CF7) and the email arrived instantly…
I think it maybe time for me to switch hosts!