Código:
Select
Ubicaciones.Nombre
From
Ubicaciones left Outer Join RelacionesUbicacion
On
(Ubicaciones.IdUbicacion=RelacionesUbicacion.IdUbicacion)
Where
RelacionesUbicacion.IdAlmacen= @IdAlmacen OR -- Ubicaciones de almacen indicado
RelacionesUbicacion IS NULL -- Ubicaciones libres
Oye y lo ocupas en la misma instruccion... tal vez seria mejor que lo hicieras en dos consultas... ya sea creando un store procedure que te traiga de forma separada los dos tipos de info...