Ich nutze auf meinem HTC momentan die App von Meebo. Das unterstützt alle gängigen IM-Protokolle wie ICQ, MSN, Jabber, etc...
Ob es einen puren MSN Client als App gibt, habe ich nicht überprüft, aber natürlich wird instant messaging auch auf dem Milestone funktionieren.