I would suggest that, in certain important events, anyone who submits a time under a certain threshold would have to submit some kind of proof that they can actually get such times, or the record would simply not be posted. That would get rid of a lot of cheating times because nobody could just go submit a 0.01 or whatever. For instance, anyone submitting a sub-10 second 3x3 average or sub-8 second single would have to provide some kind of proof. (Personally, I consider having a fast youtube video or getting a decent average in competition proof of legitimacy.) I think cubemania suffered from having a lot of unrealistic times that were not deleted simply because they were still plausible - right now, out of the 9 people with an average under 10 seconds, I have no clue who 4 of them are (so they're probably not legit) and one of them seems to have been just timing F2L. If we simply prevented records from being 'approved' once they were sufficiently fast, we'd prevent a lot of cheaters from posting obviously fake times.
I like the Wiki format, although we'd need a few moderators to make sure people don't go erasing tons of pages. One thing we could also do in that case is have articles per person (which would ideally display all of their records as well as their contact info and WCA profile link) - so for example it might go "Erik Akkersdijk 9.24 seconds" and you could click on Erik's name to go to his page. This should probably be separate from the userpages.