Not perplexing at all. Someone wrote some code that relies more heavily on statistics or has become more sensitive to a thing known as "Parameter Sniffing". It happens and, if it's 3rd party software, you don't have many choices. Either get them to "fix" it or you need to deal with it, which might require you to rebuild the indexes more often than you have in the past.