GaminggUy45: I sent an email to taketwo about releasing Nocturne and Martian Gothic Unification here hopefully something comes from it.
Here are some tips I probably should have mentioned earlier. ;) Some may be far more obvious than others.
Showing an interest is definitely a good thing, but I wouldn't recommend necessarily going after the "big-wig" publishers that aren't here, at least spending a lot of time sending emails of support. I think it's good to perhaps "remind" them of GOG's precense and show there really is interest in their titles appearing here, but rest assured that GOG is trying to get them here too.
I'd suggest seeing if there are any "abandonware" titles you like or you think would be a good fit for GOG, ones whose publisher seems to be "small-ish", or might have gone under and the rights reverted back the original developer team (Starting out on this I went through 80-ish pages of Abandonia and a significant portion of Home of the Underdogs).
For abandoned titles, finding some names that worked on the title is always good. Social media can help you get in contact with these people - Facebook, Twitter, and especially LinkedIn. I'd be careful how you use LinkedIn, though, as it is technically a site for professionals looking to advance their careers. See if they have any contact info under the drop-down button, and use that if you can (like a personal website). I have used the message option numerous times, although I do think that should be a last resort. (Putting your email in a LinkedIn message is recommend by me so they can email you if they want.)
If you're worried about going after games we've already tried to cover (although it wouldn't necessarily hurt to email the same people as it shows 2x the interest), you can use GOG's search engine to see if their name seems to pop-up in the thread. (Search from the main forum, then see if that name is associated with "The search for game rights...")
EDIT:
Oh, and for pre-1998 or so games, it's probably best to focus only on those that have DOS versions or 3D games that could utilize 3Dfx/Glide. I mention this because GOG is limited in how far they can make old games compatible, and DOS versions can be bundled in DOSBox and 3Dfx games bundled with nGlide. IAmSinistar: Well, I finally got over the terror that comes with writing to a lawyer and sent off a missive to Dr. Schiebe about Project Nomads. Will let you know if anything comes from it, or if I'm extradited to Germany for asking the wrong questions. ;)
Good stuff. :)