There are hundreds of applications and activities for MSN Messenger over at World's Best App including some games and non-games. The quality of the activities varies from unfinished to "Google Beta".

I've been playing Sudoku Sniper a bit recently which is simply multiplayer sudoku. It's quite nice to have an opponent to compete again. It can be frustrating at certain times when you are just about to fill in a square but your opponent gets there just before you.

It's certainly not as relaxing as normal Sudoku but I think I prefer it.

Tankwars is also a pretty good game. There are also implementations of classic games such as hangman, rock-paper-scissors (don't start that debate again) and battleships.