Out of office problem

I have just got back from holiday and have stopped my out of office assistant. Even though i have removed this service i am getting complaints from people out side of my company are not able to send emails to me and are getting the out of office reply. Any suggestions to why this might be happening?