il problema potrebbe essere dovuto al fatto che utilizzi UTF8, magari quei client li non lo supportano correttamente

prova a installarti thunderbird e a scaricare la posta tramite POP3 o IMAP da quelle caselle di posta in modo da vedere se effettivamente sono i client web che hanno problemi o è altro