I've seen this too with MIME::Lite, no NET::SMTP, on a sendmail server using a milter plugin....
Hope this helps

Update:

This always happened to me after restarting the milter plugin
The problem "fixed" when restarting the sendmail daemon too. Are you using sendmail or other MTA?