Firstly, GOG is completely legal.
Secondly, yes, when you first get UT2K4 from GOG you get the generic GOG key for the game. This is enough for most servers, but some servers (as I understand it, particularly those used for tournaments and leagues) need you to have a unique key.
Because of this, you can send a multiplayer key request to GOG using the relevant form from the GOG support -> contact us page (address below).
http://www.gog.com/en/support/contact/technical_issues_with_games GOG will then email you the details containing your unique key and instructions on how to put it into the game (I think for UT2K4 you'll get a couple of registry files).
Bear in mind, however, that you should expect there to be a bit of a delay between your request to GOG and them sending you your unique key. I think GOG are looking at automating the request but at present it relies on the manual request and so there is a bit of a queue considering the numbers of users and games.