Tente isto:
sudo find / -name ".message"
Estou assumindo que o comando locate
forneceu muitas informações para serem processadas, portanto, isso deve ser um pouco mais sucinto, em que ele corresponde apenas ao nome do arquivo, não ao caminho.