Wie genau äußert sich das? Im Suchfenster oben rechts, oder bei der "Auf gut Glück" Suche in der Adressleiste? Da bei mir kein Windows Messenger auf den Rechner kommt (jedenfalls keiner von Microsoft), kann ich das Problem nicht direkt nachvollziehen.
Allerdings gibt es ein ähnliches/identisches Problem mit ICQ . Kannst ja mal die Suche damit bemühen. Die Lösung für das Problem dürfte identisch sein.