Quando tive esse problema, ele foi baseado em DNS. Basicamente, quando um cliente DCHP obtém um IP de um roteador "de varejo" (ou muitos outros servidores combinados DNS / DHCP), eles adicionam uma entrada ao servidor DNS para que ping mybox
funcione.
A Apple gosta de ser um pouco diferente sobre as coisas, então eu não ficaria surpreso ao descobrir que o seu servidor DNS não tem idéia de quem é "MyMacName.local".
Avahi, não deve ter nada a ver com "resolução" do nome quando se trata de SSH (embora o Avahi possa fazer entradas em seu servidor DNS local).
Primeiro, verifique se o seu servidor DNS tem alguma ideia de quem é "MyMacName.local". Se não, eu configuraria seu roteador ou seu mac para jogar melhor um com o outro.
Em segundo lugar, verifique se o seu mac está "anunciando" o ssh no Bojour. Este link pode ajudar com isso.