Mass effect
Bioshock
Final Fantasy's
Metal gear series

Metal gear solid 1
Then MGS2(almost made me cry a bit)

then all the other games.

I'm gonna go ahead and say MGS 3.

Let's not forget Pacman, guys!

Ι could mention Bioshock and Mass Effect, but despite the fact I love them both their story is a little bit generic but presented in a unique and excellent way.
But the most deep story
Easy. two words:
Longest Journey...makes my heart pounding...

(Syberia I and II and Grim Fandago are also worth mentioning)

Ugh... I don't even know where to start. It seems that the deeper a game gets, the worse the rest of the experience is. On one hand, we have MGS2, whose story basically killed the rest of the game for me, though it attempted to be very deep... On the other hand, we have Deus Ex, which was a nice blend of the two though not truly extraordinary in either respect IMO.

Somewhere down the list are games like Mass Effect and BioShock, which only touch upon story depth but offer great gameplay.

Honestly, I don't think I've played a truly "deep" game that has handled all aspects of storytelling, intrigue, depth, and gameplay well enough to really give it any kind of accolades. Plenty of good games, plenty of deep games, not so many that combine the two. Sad, really.

Beyond Good & Evil had a pretty deep story line. Nothing like Xenogears but for an adventure game it was trying to say quite a bit.

I wonder if anyone in this thread even understands what it means to have a "deep" storyline.

Half-Life, Half-Life 2, Portal, etc

Fire Emblem Path of Radiance/Fire Emblem Radiant Dawn: I list them both because of each game has an excellent story line and Intelligent Systems did a brilliant job of connecting the two titles and showing the games story from all sides. Whether it be for Crimea, Daein, Begnion, on the Beorc side of things or from Gallia, The Bird Nations (Phoenicius, Kilvas, Heron Tribe), and Hatari's perspective on the Laguz side of things.

Mass Effect: The storyline to Mass Effect is the epitome of deep. It goes into details that it doesn't even half to. This is in spite of the fact that you character can be customized from a background standpoint. Each race has a detailed history, the characters are the definition of lifelike. The bluntness of Wrex, the endless curiosity Tali, the child-like innocence of Liara, the toughness of Ashley, I could go on but its making me want the sequel and so new DLC more.

Baten Kaitos Origins: This game took the original and fixed everything that was wrong with. The Story line was unique and well thought out. I won't spoil for anyone doesn't care to know but when you realize who your lead two characters are you can't help but feel sad.