When builds are deleted in TFS 2008, either manually or via retention policies, everything about the build is deleted, including the label. This completely removes the ability to reproduce the build in the future if the need arises.

In Service Pack 1 the capability was added to have labels preserved when the build is deleted and Buck explains how to enable this in his blog post.