For detecting cheats such as those EvilMike mentioned, my thought is to get the server to keep track of more things, and make sure what the client is doing matches with what the server knows. So long as the server keeps track of such as ammo and coins for each of the clients, we could possibly check for things like if the client is shooting a lot more ammo than the server knows they have, or if the client goes through a coin warp even when they haven't collected so many coins. I'm thinking we could also check for illegal warping by seeing if a player jumps by more than a few tiles when they're not near a warp.

Another idea that I had which would be even more complicated could be to not send information to the clients unless it is something that is within the client's possible view area. This way they wouldn't be able to know where people are on the other side of the level, or if certain items have respawned.