That is usually a Server side issue with Sendmail. It should iron itself out ina few days. If not, contact your Webspace provider and see if they have any issues going on.

I'm only speaking from experience. I had the same issue a couple times and it was my Server's sendmail. 8)

mikem