UNIONS and anything but Inner joins are always expensive.
There is alwasy a better way to do it, as long as you are using stored
procedures as the method of access.
If you are not, then you have bigger problems

The biggest issue is that both selects have to complete in entirity before
the union can begin.

Things I noticed about your Query:
 Your Collates are in series in the same column of the select.
  Only the last one would count, and it is the default for SQL.
  They should be omitted.
 The only time Collate is normally seen is when you have different
collations in the return from multiple linked servers.

Performance Hit 2 )
 always specify the schema, Database..Table Only works if the only schema
is dbo.
  It forces QA to check the sys.objects table for table ownership and
access

WAIT WAIT WAIT
 Your using a case statment in a join ??
 Your Joining to Views, I bet they are well written as this one.
 Did you put indexes on your views.
 If we are Left joining P but P.userid can't be null, THAT's AN Inner

 I understand now this is an example of how to get a 3 minute execution on
2 tables with 2 rows of data each.

Hire A DBA

SELECT

U.[Name] as UserID

, U.LastName + ', ' + U.FirstName + ' ' + U.MiddleName + ' (' +
P.PartnerName + ')' as UserName

FROM

Team..Users U with (nolock)

Left Join vwTeamPartners P with (nolock) on U.ID = P.UserID

WHERE

P.UserID is not null

and Len(U.Name) = 6

and Len(U.FirstName) = 0

and Len(U.LastName)=0

and Lower(Substring(U.Name,1,1)) ='v'

and IsNumeric(Substring(U.Name,2,5))=1

UNION ALL

SELECT

Case Len(E.EmplID)

When 6 then E.EmplID

When 5 then 'C' + E.Emplid

else null

end as UserID

,E.Full_Name + ' (' + E.DeptID + ')' as UserName

from

vwPS_Employees E with (nolock)

left join vwTeamUsers T with (nolock) on

Case Len(E.EmplID)

When 6 then E.EmplID

When 5 then 'C' + E.EmplID

end = T.[Name]

where

E.Empl_Status in('A','P','L','S')

and E.DeptID < '000'

and Len(E.EmplID) in (5,6)

and T.[ID] is not null

Order by

UserName