In MSCRM 3.0 I did a few redeployments of MSCRM and what was nice was in the database was the license table which contained the key. This was great since most of the time the customer couldn't find the original media a year down the line.
Well for MSCRM 4.0 the license table is gone, but fear not you can still get the key. If you have the media the key is in a file called license.txt (atleast according to the implementation guide). If you got the download version there is no such file but you can still get it from the MSCRM_CONFIG database in the ConfigSettings table.