Had a user who’s mailbox I moved from local exchange to Office 365 (or Microsoft Online / Online Business Productivity Suite / Azure / whatever Microsoft is calling it now) while they were on vacation and had Out of Office enabled.
Even though the Out of Office had expired, replies were still being sent, presumably by the Office 365 server – although the outlook web interface said it was off. Maybe the local exchange server was sending them although the public MX is Office 365…whatever.
The (simple) solution:
Logged into Office 365 outlook web access (outlook.office365.com), created an out of office reply, saved, and then turned it off. Ta da! No more phantom out of office replies!