R>Тогда я не понимаю, как потенциально CancelIoEx может отменять операции в других потоках -- основное назначение функции. Если IO происходит в одном потоке, а CancelIoEx — в другом, то завершение IO и CancelIoEx по определению происходят одновременно. Следовательно состояние OVERLAPPED может меняться из PENDING в "завершено".
R>Мое понимание, что CancelIoEx можно звать даже для уже завершенной оперции. В этом случае она возращает документированный код возврата ERROR_NOT_FOUND.

Да. Тут вы правы. Должна работать независимо от статуса операции.
Попробовал воспроизвести у себя — не получилось (10 минут на Win7 SP1 + all updates).

И как же этот алгоритм реализован под WinXP ?
Я бы лучше ввёл отдельный сигнал завершения PENDING-операций и использовал WaitForMultipleObject (проверено временем).