Finally tracked it down. The CO had routed it to the wrong DID. It was supposed to be routed to xx65 and was actually going to xx60. We had previously used xx60 to route to a MCG containing xx65 before it was moved to the offsite call manager. Since the MCG programming was never removed, the calls were behaving correctly, but it was going to the xx60 mailbox when it hit voice mail, which no longer exists, causing it to roll to the auto-attendant by default.

When in doubt, blame the phone company!