Дело в том, что get_NewEnum у меня возвращает IUnknown самой коллекции. А вот когда из него делают QI для какого-нибудь IEnumXXXX, то создаётся новый объект, реализующий этот интерфейс (сделано через COM_INTERFACE_ENTRY_TEAR_OFF).
Поэтому он мне каждый раз возвращает один и тот же IEnumVARIANT. Если сделать на нём Reset, то всё работает нормально.
Вообще, это не очень здорово. .NET мог бы и сам вызывать Reset, для избежания подобных недоразуманий.