I can reproduce this behavior; I find many tasks in our system where the date “Last Modified” is later than the date “Completed At”…sometimes by more than 2 years. In none of these cases, did the history trail within the task give any indication as to what happened to create the record of modification in, say, Oct 2019 for a task that was completed as of March 2017 and obsolete for all purposes shortly thereafter. (But, as we all know, history items can be deleted and people often do as otherwise they can build up and hide data of interest.) So I would suggest that it may not be the Sort function at fault; the trouble may be in whatever process is creating unexpectedly late dates of modification for long-closed tasks.
11384, when you click into one of the tasks you did not expect to see in your search, do you see a recent date of modification (i.e. one that fits with the search and sort you have chosen)?