wenn du xn--mller-ha.de als punycode erhälst, hatte der übergebene string möglicherweise kein korrektes encoding. wenn du sicher weisst, dass der string utf8 ist, versuch mal das utf8-flag explizit zu setzen: _utf8_on($domain);
dann wie gesagt den string in secondlevel und toplevel trennen und den secondlevelteil encode() übergeben.
wenns dann noch nicht funktioniert, würde ich mich mal genauer bei Encode einlesen (bin leider auch kein utf fuchs^^)

btw. zum prüfen: der korrekte punycode für müller.de ist xn--mller-kva.de