We've heard from a few customers that they would prefer not to have the build labels deleted when builds are deleted. In Team Foundation Server 2008 SP1 we added a feature to control whether build labels are deleted when the build is deleted. This feature is really a stop-gap measure, and it changes the behavior for build deletion on the entire server (i.e., you cannot change it for particular build definitions). In TFS 2010, we've added GUI options to allow you to control this for each build definition, and the setting is stored in the database along with the build definition.
To use the feature in 2008 SP1, add the following to the appSettings section in the web.config on the server (application tier).
<add key="PreserveLabelsOnBuildDeletion" value="true" />
It's not clear at this point whether the TFS 2010 upgrade process will be able to automatically migrate this setting to the build definitions. In the worst case, you may need to enable this setting on each build definition after upgrading to TFS 2010.