¿Cómo usar JOIN en lugar de UNION para contar los vecinos de A O B?

La respuesta de @Martin es correcta. Es un genio.

¡Vamos Martín!

CORRECCIÓN

Su respuesta funciona con 1 pequeña modificación si se ejecuta en contra de la solución bidireccional que di. De lo contrario, los resultados son incorrectos.

Así que tu respuesta es suya y mía :)

La solución 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