I've also been experiencing this problem as well. The story I got was that their mail server/queue or whatever is overloaded and giving a 500 error, permanent error that address is not available, rather than a 450 error, temporary error that mailbox in unavailable. Sean