Eureka

¡Lo encontré!

Me estaba volviendo loco. Al ensamblar todo el conjunto el relé se quedaba siempre conectado. El pin 12 estaba siempre HIGH y no sabía ver porqué. 

Finalmente me he dado cuenta de mi error. En la documentación de la Proto Shield dice claramente que:

The ICSP connector available on the shield has his connections wired directly to the SPI pins of Arduino

MISO connected to D12

Y eso era. Para sacar los 5 V que necesitaba para el relé y el bus I2C de los sensores de ultrasonidos, me estaba apoyando justo en el acceso del conector ICSP que está al lado, el del pin 12.

¡Era yo el que lo estaba poniendo a HIGH por hardware!

En fin. Errare humanum est