Да, верно, если у вас random-access итератор, то это так и будет (честно говоря, особо ковыряться в коде не хочется)
И в любом случае — выборка по индексу из массива не может быть (!) медленнее поиска, пусть даже как Вы утверждаете, и в упорядоченой последовательности.
А скорость как раз нужна. Когда по окнам пробегают много сообщений — это уже становится накладно. А насчет WTL — да, ошибся, там действительно switch только на MessageMapId. Печально.
А насчет мнения о win32 — fine, оно Ваше, но необязательно выражать его так категорично.