One other question came to mind: In what order are the uniqueidentifiers being added to the TVP as they are sent to the SQL Server? If you're using .NET then is it safe to assume the rows are in "any old order" in your DataTable or can you confirm they are sorted?
And a bit more on this:
My initial testing showed if there less than 100 records in that tvp then it actually performs worse than the older one which doesn't have any index on it. I was hoping that it would perform same if not better for smaller datasets.
The point where the performance gain the proc has with the index in place outweighs the overhead the engine imposes having to sort the rows as they are added to the Table-type sounds like it is at ~100 rows. Like I said though, the hint you give the engine by having the clustered index in place in terms of which order to process the data when it comes to joins will help you avoid deadlocks in concurrency-scenarios.
There are no special teachers of virtue, because virtue is taught by the whole community.
--Plato