Funny how most of the odd problems that I run into have to do with Plesk. This error randomly started happening one day when trying to send email to any user on a Plesk windows server:

503 This mail server requires authentication when attempting to send to a non-local e-mail address. Please check your mail client settings or contact your administrator to verify that the domain or address is defined for this server.

All the mailboxes were enabled. Mailenable relay settings looked OK. Maybe something happened with Plesk? I just repaired all the mailboxes for the heck of it:

%plesk_bin%\mchk.exe --all --fix=local

Error magically fixed!