Since updating to 1.9.2 this hasn't happened.
I had already checked with the mailserver and the service provider and they insist that we are typing the email incorrectly. Problem is, we don't type the email after initial configuration. It's so random making it hard to replicate and put my finger on it.