Well, I spoke too soon. It appears that fsolve is broken, or at least behaving differently than what I am used to (and my main version of Maple has been 2015 since I had too many issues with the later ones).
The specific use case is a strongly oscillating function (a sine with some high-ish frequency) where I need to pick a specific zero crossing, which I do by giving fsolve a reasonably close initial estimate. That works fine in 2015. In 2022 it returns 0 for all my cases, which is correct but not the zero I want. So it appears fsolve is jumping ahead or back way too aggressively.
I am sure this can be prevented by using intervals and the avoid option, but it seems like a step back. Now, a comment in the Help for fsolve says it got updated in Maple 2018, so maybe that is where the problem arose.
I guess I am a little less excited now. This situation is in a part of code I am using daily right now and cannot afford not to work.
Edit: It turns out this is the old issue in fsolve when using "Usehardwarefloats:=true" (instead of the default "deduced"). So maybe it is not a new problem, although having such a bug hanging around for this long is unsettling in itself.