But it's definitely an interesting and intriguing, if totally useless, question: What is the slowest possible algorithm for a problem that "doesn't waste time"?
That said, Slowsort is still my favourite, for it has all the properties of a good sorting algorithm: stable, easy to parallelize, easily proven correct, easily made in-place.
I think one way to make the question well formulated is to have a series of primitives, each of which has some chance to get to the end of the algorithm. The "best" algorithm is the one generating the longest expected sequence of primitives from a given problem.
Without that, it doesn't seem like there's really an answer to the problem since a program can go indefinitely slow by mixing-in all manner of extra work.
Anyway, a real world analogy is walking through a mine-field - obviously, the aim to not find a land mine as many "search" actions as possible.