Is it possible that the Game Genie has a more snug fit than a Genesis game? Perhaps you need to gently bend the connector pins in the console to get a tighter fit.

As far as cleaning goes, take a clean dry game and repeatedly insert and remove it. If it gets dirty, clean the game, dry and repeat.