OK, continued searching has yielded results, which I'll document here for the next person.
This link pretty much described my problem and led me to my solution. The reference to this bugzilla entry provided the proper commands.
The problem is that Zimbra only checks the "To:" header when deciding whether to send an OoO message, and it must match the zimbra account. In my case, an upstream MX host receives all inbound email for USER@MYDOMAIN.COM and rewrites Zimbra server-bound email as USER@ZIMBRA-SERVER.MYDOMAIN.COM, which is what all the Zimbra accounts look like. Whenever the Auto-Reply is set for an account, and the "To" header of an incoming message does not match the account address, an auto-reply is not send and you see entries like this in ~zimbra/log/mailbox.log:
... outofoffice not sent (not direct) ...
The fix is to add a new preference variable for the account that acts as a sort of 'alias' that the Out of Office logic can use to test the "to" headers against. It can only be set via command line, I couldn't find it in the web console. Run the following as the 'zimbra' user:
That was it. Problem solved. The old admin must have done that for existing users, but I never knew to do this for new users, which is why it was only happenning with new users.
$ zmprov ma USER zimbraPrefOutOfOfficeDirectAddress USER@MYDOMAIN.COM