Seems like this is Bug 14129,
Bug 14129 - no 550 unknown recipient rejection or out of office replies for alias domains, but I don't really see how to fix the problem based on the comments in the bug thread.
Comment #1 indicates that instead of using domain aliases one should use "real account aliases", but I can't find any documentation of how these differ from other aliases, which doesn't work.
Seems like my situation matches the description in comment #8, most of our accounts are supposed to get mail regardless of what domain the mail is sent to.