Labels are an interesting part of version control system. In version 1 of TFS Version Control, labels do not contain deleted items. 

Here's an example sequence of commands that shows this behavior: 

mkdir dir
echo dir\a.cs > dir\a.cs
echo dir\b.cs > dir\b.cs
tf add dir /r
tf checkin /i
tf delete dir\a.cs
tf checkin /i
tf label label1 $/;T /r
tf lables label1 /format:detailed

The labels command returns this data:

Label  : label1
Scope  : $/
Owner  : bill
Date   : Thursday, March 22, 2007 4:04:34 PM
Comment:

Changeset Item
---------     ------------------
1              $/
2              $/1
3              $/1/dir
3              $/1/dir/b.cs

As you can see $/1/dir/a.cs;X1 is not returned from the label. There is an ambiguity when you compare the items in a label against another version specification (changeset, label, etc...) When you do the comparison it is not possible to determine if an item is missing from the label because it was deleted, or because the item was deliberately excluded.

Merging with a label will not merge file/folder deletes into the target tree.

Here is an example that shows you what I mean:

mkdir src
echo src\a.cs > src\a.cs
echo src\b.cs > src\b.cs
tf add src /r
tf checkin /i
tf branch src tgt
tf checkin /i
tf delete src\a.cs
tf checkin /i
tf label label2 $/;T /r
tf merge src tgt /r /version:Llabel2

The merge command will report correctly that there is nothing to merge because src\a.cs does not exist in label2. 

Team Build runs into the same issue when it computes the changesets that are new with the current build. In order to do this Team Build compares the label for the last successful build and the label for the current buld. A heuristic is used to determine what it treats as deletes when comparing two labels. If an item is in the first label and not in the second label then the version control server is asked if the item's path exists at the latest changeset in a non-deleted state. (VersionControlServer.ServerItemExists) If the item doesn't exist then it is reported as deleted. If the item does exist then it isn't reported as a difference at all. If you currently merge using labels you could implement the same heuristic in order to ensure that deletes get merged. You would probably want to review the suggested deletes manually before checking in the merge.

Bill