The other odd thing is I have a game called Deus in my library now, which I don't recall buying. It is also not listed on their site when doing a search, only the 2 Deus Ex games, Deus Ex GOTY and Deus Ex 2: Invisible War.

Just did a quick check on my GOG account and nothing's missing, all the games I purchased are there.

Add

/refresh to your URL when you're at the account page and press enter.

Well, I did a refresh and that didn't change anything. I own Deus Ex: GOTY edition on Steam, I wonder if I'm getting my services confused? I could have sworn I bought it on GOG when they had a 75% off sale. Or one of the holiday sales (just so I could have a copy that was not tied to Steam - yeah, I'm paranoid).

Also, that doesn't explain the Deus game that I have on my shelf (some sort of robot/mech game) that doesn't appear as being listed for sale. Unless it was one of those freebies that has since been removed from sale.

Well, some games have been removed from the catalog, but they stay on your shelf if purchased. As for having bought the game, you could check your Emails or PayPal history. Worse case Email them for a history. I did a search in my Outlook and I bought it on Steam: The Deus Ex Collection 2.99 USD 😀

I checked because I know I have all the Deus Ex games, too. Mine wasn't from GOG, though. I got mine through Steam, most likely as a giveaway because I only have 2 games that I bought registered to my Steam account and those were games that I bought in DVD form. Everything else is freebies.

I have had Fallout 1 disappear from my GOG shelf a few times. It has always returned after a while (~next day).

I checked just to be sure, my both Deus Ex games are still in my list. And as far as I can tell, there are no missing titles from my library.