So as it turns out, enumerating user-space pages using VirtualQueryEx isn't prohibitive at all. For a typical process it takes roughly ten times as long as a single call to QueryWorkingSet, but that's well within the bounds of practicality. On my modest machine the operation takes somewhere in the order of 1ms in native code, and 100ms for .NET with interop.

Still, if anyone has any ideas why NtQueryVirtualMemory is being so uncooperative, it would be enlightening.

Admiral