It sounds like something changed from the original usage expectations, or said expectations were not accurate begin with. The query plans are just another cog in the machine. I would consider it normal for them to be re-evaluated periodically under real life circumstances (or if either the application, or its "application" knowingly changes.)