It happened quite a lot to me :
Laser Squad : When I first played it at my cousin's house, I fall in love with the Action Points/ reaction fire mechanisms, the mission based structure, and the loadout allocation. Then I could not find the game at all until like 10 years later.
Civilization : I played the first one to death. It was one of the last games to come to Atari ST (and the loading times were atrocious).
Warcraft 2 : I developed another obsession for this game, as I still had an Atari at the time, which prevented me from playing it, or any RTS for that matter (there were strategy games that were in real time, but no RTS).
Lords of the Realm 2 : The ancestor of the Total War games. Too much micromanagement, but at the time, it felt good. I really liked dropping boiling oil on castle besiegers, and leveling castle walls with catapults.
Fallout 2 and Baldur's Gate : My first PC RPG (I only played RPG on Atari before, mostly Dungeon Master clones), and they both were amazing in their own way. I imagined RPG greatness that never came after that (although PST had a glimpse of it, and BG2 was quite an upgrade over BG).
XCom : I got to this one pretty late, but it made up for not finding Laser Squad (although it lacked the multiplayer of Laser Squad). Fighting these squad battles over a reason made the gameplay even more compelling.
Kohan: An RTS that blended concepts of supply, formations, units, and traditional RTS concepts. The ideal blend of traditional strategy games, and RTS, not too hectic so that APM was hardly a concern, and it felt like a RT HOMM. Too bad it had a subpar sequel, and no game to take over this niche.
Warhammer 40K: Chaos Gate : "The emperor orders you to die!" Nuf said. My first encounter with ironman mode, and I really loved the way it affected the game.
Shogun Total War: Lords of the Realm 2, without the overburdening micro management, and awesome visuals : That felt like a dream come true. Too bad they made the sequels micro management heavy.
Independance War: Edge of Chaos : semi Newtonian physics, semi open gameplay, piracy in space? Wow. Sadly, it was the end of the space sim genre.
Not much afterwards, as games became frozen into established genres, and surprises were few.
Edit : Forgot Operation Flashpoint. This FPS really made you feel the tension of risking your "life" like none other at this time.