Grabbing at straws here: Red Alert 2?

A stretch, but it could work. Assuming they are all cover images like the OP implies there was certainly red and black on the red alert cover. Road Rash works for outlaws at a stretch.

Still, it feels like we are forcing it where as it came naturally for Lucasarts.

Yes it's round holes and square pegs. At the moment Lucasarts are the only choice that ticks all the boxes and given the experience with the Activision build up it makes sense to go with the obvious choice.

Well "Alice" would fit there - if you know the story, the game is about her being in an asylum after going through hell...

2K Games.

Is there a way to see the first three backgrounds? I want to think about covers.

As much as I'd love that to be true, the clue's text was plainly western themed.

Lucasarts remains the most likely candidate. After all, remember that GOG's clues are kind of blatant. There's no point in reading between the lines when the lines in question are usually big tubes of neon that GOG have erected in the shape of the words "CLUE, GUYS! LOOK HERE!".

What about Wasteland for fear your past?

Brian Fargo bought the rights to Wasteland from EA so it's now a property of InXile.

'Kay...

Who owns Desperados?

I find it hard to believe that EA never made a western game.

Infogrammes/Atari

Just realized the term "outlaws" is used a lot on Oddworld: Stranger's Wrath, which was confirmed as coming to GOG on the Steam forums by the head developer of the PC port. It had a Western theme as well.

Obviously the issue there is that EA only published the Xbox version. It could however mean that all the clues are not necessarily from the same publisher? Maybe it is just games they are announcing as coming soon in general.

I'm reaching, but my issue here is that if the underworld clue came out first I would have been sold on EA being the publisher. It's only because Outlaws came first that I was sold on Lucasarts. Both of those are very compelling clues. Yes, Grim Fandango can be used for Underworld, but just barely.

If it's EA, I'll be more excited than if it was LucasArts.

For instance, CRUSADER: NO REMORSE.