Probably the game that our group has gotten the most replay value out of is Mutant Chronicles: Siege of the Citadel. I'm not sure if it's still in production, but I see copies of it nearly everywhere I go, so it should be available.

In this game, one player controls the Mutants, while up to four other players control teams of Doomtroopers (if you are familiar with the Mutant Chronicles RPG background, you should understand). It is a board game, but played with miniatures, and you get a bunch of 'em with the game (all plastic, and not very detailed, but certainly functional.

It's a nice, simple little game with next to no book-keeping, some innovative game mechanics, and is its own "campaign" system, allowing you to play ten separate missions in a row.