Como usar JOIN em vez de UNION para contar os vizinhos de A OU B?

A resposta de @Martin está correta. Ele é um gênio.

Vai Martinho!

CORREÇÃO

Sua resposta funciona com 1 pequena modificação se executada na solução bidirecional que dei. Caso contrário, os resultados estão incorretos.

Então sua resposta é dele e minha :)

A solução completa:

DECLARE @T1 TABLE (calling_party VARCHAR(50), called_party VARCHAR(50))

INSERT  INTO @T1
SELECT  *
FROM    dbo.monthly_connections_test

INSERT  INTO @T1
SELECT  *
FROM    (
        SELECT  called_party AS calling_party, calling_party AS called_party
        FROM    dbo.monthly_connections_test AS T2
        WHERE   T2.called_party < T2.calling_party
        ) T2
WHERE   NOT EXISTS (
        SELECT *
        FROM    monthly_connections_test
        WHERE   calling_party = T2.calling_party and called_party = T2.called_party
)

select u1, u2, count(called_party) called_parties 
from (
select distinct u1, u2, called_party from 
(
        select a1.calling_party u1, a2.calling_party u2 from 
        (select calling_party from @T1 group by calling_party) a1,
        (select calling_party from @T1 group by calling_party) a2
) pairs,
 @T1 AS T
where
(u1 <> u2) and 
((u1 = t.calling_party and u2 <> t.called_party) or
(u2 = t.calling_party and u1 <> t.called_party))
) res
group by u1, u2
order by u1, u2