Acontece que o culpado foi /etc/resolv.conf
. Mudando:
search <myprovider>.at
nameserver ...
nameserver ...
nameserver ...
para
search <myname>.at <myprovider>.at
nameserver ...
nameserver ...
nameserver ...
corrige o problema.
(Vou deixar a questão em aberto por enquanto, apenas no caso de alguém poder dar uma explicação para isso.)