It was some time ago, but I've had similar trouble. Back when I had a small webhost (I stopped when shared/reseller hosting descended too far into an overselling-and-deliberately-misleading-advertising-to-compete-on-price race to the bottom) a customer who "left" (was told to get lost due to non-payment) demanding I keep his content up because some users were still ending up there. As far as I could tell me of the records had ever had a TTL longer than the four hours )my default) while they were pointing at that address, yet more than a month later some traffic was still coming in to that address for that domain. I didn't look too deeply into it due to the history of the client in question, but it was certainly a real problem at that point in time.
So for my own stuff if there is a controlled change I try to keep the original address operating as a relay to the new address for a chunk of time, and for a while after that have it host a message saying "your DNS resolution seems to be broken, you shouldn't have been sent here, please report this to your ISP or local SysAdmin, if you want me to try fix it for you here is a list of my consulting fees".
So for my own stuff if there is a controlled change I try to keep the original address operating as a relay to the new address for a chunk of time, and for a while after that have it host a message saying "your DNS resolution seems to be broken, you shouldn't have been sent here, please report this to your ISP or local SysAdmin, if you want me to try fix it for you here is a list of my consulting fees".