Isso não é possível sem enviar uma mensagem e esperar algum tipo de retorno, principalmente sem o conhecimento do destinatário. E para hospedagens de e-mail que oferecem caixas postais do tipo catch-all, aí que você não vai ter certeza mesmo.