The CPU power to do it is negligable. When the Flash move (running client side) is done playing the game, it can MD5 the score + some secret string and then pass the MD5 result AND the score in plaintext to the server. The server MD5's the score + the secret string. If the MD5 result matches the MD5 result that the Flash movie passed in, then you can be reasonably sure that the user isn't altering the score en route.
The user could dis-assemble the Flash movie to find the secret string and then construct their own HTTP request to pass in a fake high score but that's probably more work than most people want to do just to be the high score champion.
But in general, you're right: If there were a $1 Million prize for the high score, then it would be worth it for a hacker to spend a few hours to crack the code but I doubt that you're offerring a $1 Million prize.
You could obfuscate the whole process like timing the game, building an array of the actions that happened during the game, and communicate with the server during the game to report progress which makes it even harder for the hacker to simulate a game... but if the incentive is high enough, hackers will spend the time to do it.
This is why the term, "trusted hardware", was invented. If you could somehow insist that the user play the Flash movie on a motherboard, hard drive, CPU, and network card that you supplied, then you could check to see if they were tampered with and then you could be assured that the reported high score was real... but that's only realistic with products like with iPods, cell phones, ATM machines, and voting machines where you supply the hardware. Running software on the user's machine forfeits your guarantee that the data is not altered.
