Remember that you don't need perfection: you need people to believe that they're likely enough to get caught that they don't want to use a pre-canned cheat, and you need just enough cheat detection mechanisms to make it hard for people to make new cheats. Not all of that has to be technological: you can spread rumours that your cheater ban waves are bigger than they actually are, for example, and that'll keep more people from even trying in the first place.

You don't have to trust the timestamp - and you shouldn't. You can use a bunch of methods to go from untrusted to grudgingly accepted: requiring monotonicity means cheating clients have to be permanently slower rather than selectively slower. Having tolerances for out of order packet rates or accepted deltas before discarding player actions will have some false positives for players on terrible networks, but will also reduce the impact of any possible timestamp-related cheats.

It can't be fully solved server side, not without sacrificing acceptable performance. I reckon it can probably be dealt with enough on server side to keep cheating to a tolerably low level. It's probably cheaper to just license a windows rootkit though.