domgrief: Given that [url=http://www.nwlink.com/~dberke/images/ex1scr1.gif]one of the screenshots[/url] from Excelsior's website is from the same room as Kalirion's screenshot, I'm going to take that as proof.
(Regarding your mention of the annoying labyrinth, that reminds me of most of the hours that I've spent playing nethack :)
For your guessing pleasure, here's a game of roughly the same vintage as Excelsior, as well as GOG's latest release, Raptor.
(Note: google fu or tineye fu will net you the game name pretty quickly. Try to use your grey matter!)
You are of course correct about Excelsior (Phase One, Lysandia)!
And your game is
Traffic Department! A game with great story and writing, but so-so gameplay.
tineye is the reason I took my own screenshot, but I actually knew this one :)
I'll let someone else have a turn now, since I can't take any game screenshots for another 4-5 hours...