R12 Workflow: Automated replies give "Client was not authenticated" errors

On R12.1.3 and R12.1 "Automatic Reply To Unsolicited Mail shows erros 530 5.7.1 Client was not authenticated" from MOS document ID 1991613.1 indicates this can be resolved with a patch but it seems like the root cause is when the SMTP server gets changed!