How To Design The History Table To Be More Efficient?

I am running a website of crossword puzzle and Sudoku games. The website is designed to be:

There are 20-30 games onlines each day.
Every registered user could play and submit the game to win scores.
For each game, every registered user could get the score for ONLY one time. i.e., No score will be calculated if the user had finished the game before.
To avoid wasting time on a game finished before, user will be notified with hint message in the page when enter a already finished game.


The current solution is:
3 tables are designed for the functions mentioned above.

Table A: UserTable --storing usering information, userid
Table B: GameList --storing all the game information.
Related fields:
GameID primary key
FinshiedTimes recording how many times the game has been finished
Table C: FinishHistory --storing who and when finished the game
Related fields:
GameID ID of the game
UserID ID of the user
FinishedDate the time when the game was finshied

PS: Fields listed above are only related ones, not the complete structure.

Each time when user enters the game, the program will read Table B(GameList), listing all the available game and the times games have been finished. User could then choose a desired game to play.

When user clicks the link and enter a page showing the detail content of the game, the program will read Table C(FinishHistory) to check whether user has finished this game before. If yes, hint message will be shown in the page.

When user finishes the game and submit, the program will again read Table C(FinishHistory) to check whether user has finished this game before. If yes, hint message will be shown in the page. If no, user will get the score.

Existing Problems:
With the increase of game and users, the capacity of Table C(FinishHistory) grows rapidly. And each time when a game is loaded, the Table C will be loaded to check, and when a game is submitted, the Table C will be loaded to check again. So it is only a time question to find out Table C to become a bottleneck.

Does any one here have any good suggestions to change / re-invent a new structure or design to avoid this bottleneck?