"Vimos castelos por todo o lado na praia" deveria validar.

(E "Vimos castelos por toda a parte na praia", que não testei, também).

Em pt pt "em todo lugar" deveria ser "em todos os lugares"

e "lugar" é um sítio bem definido com características próprias (daí a existência de não lugares). Numa praia, lugar seria a própria praia, o sítio onde temos a toalha, o sítio onde os nossos amigos têm as toalhas deles, o apoio de praia que frequentamos etc. A areia da praia onde se pode construir castelas não é um lugar, mas para a criança que construiu um determinado castelo, esse ponto no espaço passou a constituir um lugar.

O pt pt não usa expressões como "todo dia", "toda hora", "todo lugar", etc, a expressões equivalentes seriam "todos os dias", "todas as horas", "todos os lugares"...

"Vimos castelos por toda a parte na praia"

não valida mas corrige para:

"Vimos castelos em toda parte na praia"

Quando usamos o "em" nesta frase, estamos a dizer que em cada uma das partes da praia, havia pelo menos um castelo.

O "por" usa-se quando as coisas estão espalhadas desordenadamente, ao acaso, o que parece ser o caso: para onde quer que olhássemos, víamos castelos.