I'm having the same issue. I'm with BT but my email is redirected from a 1and1 hosted account. I receive some emails fine, but others get bounced back with the error message listed by MatthewL above. One of my colleague also has a BT email address but I only receive half the mails she sends me, which makes me wonder if it's a BT problem?
Has anyone managed to sort this out? I don't know where to start and as I work from home it's affecting my work emails.