Just posting few that came in mind..

All Silent Hill games & soundtracks are awesome so this way too difficult.
(I even like Silent Hill Origins and Shattered Memories.. X-)
Just picked two because of the moments when they appear in game giving that "feeling".
Silent Hill 2 - Magdalene (Oh darn that moment in the game.. Sad sad..)
Silent Hill 2 - True (Again that moment in the game..)

Metal Gear Solid..
Introduction
Encounter (Oh crap, need to hide fast..)
Aoife Ní Fhearraigh - The Best is Yet to Come , The Ending Credits version (Warning for post-credits talk/spoilers)

One arcade game music that I still listen for the memories (insert coins..)
Outrun - Magical Sound Shower , Live version by Sega's official in-house band S.S.T.Band.

Commodore 64:
Ocean Loaders (press play on tape. and wait..)
Rob Hubbard - International Karate
Rob Hubbard - Delta in-game
<insert more Rob Hubbard here> X-)

Amiga:
Xenon 2 Megablast main theme
Allister Brimble - Alien Breed main theme

Loaning from OP's list:
Halo main menu, Deus Ex main theme, Cannon Fodder.. very good choices.. :)

Probably have to post more later..

A few I left out unintentionally,

The Neverhood, Skullmonkeys & Boombots - the entire album is a collection of tunes from the great Terry Taylor for games Doug TenNapel (of Earthworm Jim notoriety, among other things) worked on. Anyone familiar with the games is undoubtedly a fan of the music. And if you aren't, you should get on that ASAP. I'm looking forward to seeing what he does with Armikrog.

Headhunter - fantastic score by Richard Jacques. The score he did for the game's sequel, Headhunter: Redemption, wasn't quite on par with the work he did previously (not owing to the fact that one is performed by live orchestra and the other not - quality sound is quality sound surely) but Headhunter is one of his masterpieces.

and since I've mentioned Jacques I guess I'll add in the entire collection of music from Jet Set/Grind Radio. Few games have such an eclectic representation of music on display as that game did/does. Unfortunately no officially complete soundtrack (including all the regional song variants that were put in the game throughout various points) has been made (licensing fees being the biggest cockblock in that department, I'm guessing) but the Sumthing Else release is as good as things will get for now.

(again no links as I'm under restriction from including them at this point in time but like before most of the above should be readily available on the YouTubes)

Heroes 3 of might and magic, especially the Stronghold and the Necropolis themes.

http://www.youtube.com/watch?v=TSoPiffmSYU

Old games have better music overall in my opinion, now few games have great and memorable osts.

I'm a big fan of the Fallout 1 and 2 soundtracks by Mark Morgan. You can download many of the tracks in high bit rate digital form for free (fully legally) as part of the Vault Archives.

Some other game tracks I find very good are:

Harvest Dawn from Oblivion by Jeremy Soule
Outlaws Theme from Outlaws by Clint Bajakian

The Machinarium and Bastion soundtracks are quite good from more recent games.

Just to name those I can think of at the moment:
Turrican Soundtrack

Turrican II Soundtrack

Crusader: No Remorse - Soundtrack

Crusader: No Regret Soundtrack

Jets'n'Guns - Soundtrack

Unreal Gold Soundtrack

Unreal Tournament Soundtrack

C&amp;C Tiberian Dawn Soundtrack

C&amp;C Red Alert Soundtrack

Deus Ex Soundtrack

Endless Space sountrack. One of few collections I can listen without single "turn that off" tune. Usually I listen it when I need to concentrate on work.
Though I think other Amplitude's works are as fine as that, they just still from games considered "Early Access". I mean Dungeon of the Endless, and Endless Legend.

Lotus Turbo Challenge 2

And naturally every Turrican. I wonder who holds Turrican rights these days.

Turrican 1

Turrican 2

Nostalgia-man edit: Amiga era had seriously most distinct game music.

These days soundtracks tend to be too "2 steps from hell" sort of generic movie stuff.

Someone mentioned the Command & Conquer: Red Alert soundtrack, so I add Command &amp; Conquer: Red Alert 2 soundtrack

Also the Age of Empires III soundtrack

Absolutely wonderful fairy tale like games and OSTs:


Trine 1.
https://www.youtube.com/watch?v=RkyhqPjVE0w

Trine 2.
https://www.youtube.com/watch?v=8fkSw8Auv3I

Magicka.
https://www.youtube.com/watch?v=Xc9n72rH1Ow

Fable - The Lost Chapters.
https://www.youtube.com/watch?v=BCXTmBAk5C0

Bonus:
Faster Than Light.
https://www.youtube.com/watch?v=ygH9VcV7IBg

Castlevania: Symphony of the Night has been mentioned before. That'd be my all-time favorite game OST.
Crystal Teardrops in particular sets the mood when entering the underworld.

Castlevania: Curse of Darkness, Baljhet Mountains, sweet melancholy of eternity.

Last Ninja, The Wastelands. Get INSTA-PUMPED!!!

ZOIDS, one of many Rob Hubbard's greats for the C64.

Well everybody loves the classics so I tried to be sneaky:

http://www.youtube.com/watch?v=0n2Y3VsAE3c
plenty of others but how can nobody like this?

http://www.youtube.com/watch?v=MTpBwYpK7Zs&amp;index=10&amp;list=PLD8C5408C90465C0D
best electro/techno ever!

http://www.youtube.com/watch?v=dlNOZ1D6zgY
sadly in need of proper release in english regions...sigh

http://www.youtube.com/watch?v=HiimIwGVAQQ
Burning Windmills Rock!

Xenoblade has some of my favorite video game music: http://www.youtube.com/watch?v=bl9dP0CJfbQ

Castlevania: Symphony of the Night has gotten mention, but I like the Rondo of Blood OST a little more:http://www.youtube.com/watch?v=cdSsN_uzv-c

Baten Kaitos series has some of the best music in games: http://www.youtube.com/watch?v=bDVoYszw69M
http://www.youtube.com/watch?v=KK8cs3LMGhM

Phantasy Star IV: http://www.youtube.com/watch?v=GQQXKH_XXh4

I actually own the CD's for Xenoblade, Symphony of the Night, and BK: EWatLO.
Looks like somebody beat me to it.

The Prince of Persia Forgotten Sands soundtrack has some great stuff in it and the main theme is one of the best sounding things I feel like I have ever heard. https://www.youtube.com/watch?v=RJ4QmmwENtA

I also like the Witcher soundtracks.

The Trine soundtracks are a good listen. They are a bit of their own sort of thing, but I think it's a really well done sort of thing. It's hard to pin any single track as they are all quite consistent.

There are a few good Assassins Creed ones like Ezios Family https://www.youtube.com/watch?v=O0i6YFrSs6c

This Gears of War 3 track https://www.youtube.com/watch?v=rxgTlQLm4Xg

Doom.