To elevate what jocull mentioned in a comment, I was doing everything mention in this thread and striking out... because mine was in a loop to be run over and over; after the first time through the loop, it would sometimes fail. Always worked the first time through the loop.
To be clear: the loop includes the creation of SmtpClient, and then doing .Send with the right data. The SmtpClient was created inside a try/catch block, to catch errors and to be sure the object got destroyed before the bottom of the loop.
In my case, the solution was to make sure that SmtpClient was disposed after each time in the loop (either via using() statement or by doing a manual dispose). Even if the SmtpClient object is being implicitly destroyed in the loop, .NET appears to be leaving stuff lying around to conflict with the next attempt.