How can virtual texturing actually be efficient? For reference, what I'm referring to is the "generic name" for the technique first(I believe) introduced with idTech 5's MegaTexture technology. See the video here for a quick glance on how it works.

I've been skimming some papers and publications related to it lately, and what I don't understand is how it can possibly be efficient. Doesn't it require constant recalculation of UV coordinates from the "global texture page" space into the virtual texture coordinates? And how doesn't that curb most attempts at batching geometry altogether? How can it allow arbitrary zooming in? Wouldn't it at some point require subdividing polygons?

There just is so much I don't understand, and I have been unable to find any actually easily approachable resources on the topic.
Overview

The main reason for Virtual Texturing (VT), or Sparse Virtual Textures, as it is sometimes called, is as a memory optimization. The gist of the thing is to only move into video memory the actual texels (generalized as pages/tiles) that you might need for a rendered frame. So it will allow you to have much more texture data in offline or slow storage (HDD, Optical-Disk, Cloud) than it would otherwise fit on video memory or even main memory. If you understand the concept of Virtual Memory used by modern Operating Systems, it is the same thing in its essence (the name is not given by accident).

VT does not require recomputing UVs in the sense that you'd do that each frame before rendering a mesh, then resubmit vertex data, but it does require some substantial work in the Vertex and Fragment shaders to perform the indirect lookup from the incoming UVs. In a good implementation however, it should be completely transparent for the application if it is using a virtual texture or a traditional one. Actually, most of the time an application will mix both types of texturing, virtual and traditional.

Batching can in theory work very well, though I have never looked into the details of this. Since the usual criteria for grouping geometry are the textures, and with VT, every polygon in the scene can share the same "infinitely large" texture, theoretically, you could achieve full scene drawing with 1 draw call. But in reality, other factors come into play making this impractical.

Issues with VT

Zooming in/out and abrupt camera movement are the hardest things to handle in a VT setup. It can look very appealing for a static scene, but once things start moving, more texture pages/tiles will be requested than you can stream for external storage. Async file IO and threading can help, but if it is a real-time system, like in a game, you'll just have to render for a few frames with lower resolution tiles until the hi-res ones arrive, every now and then, resulting in a blurry texture. There's no silver bullet here and that's the biggest issue with the technique, IMO.

Virtual Texturing also doesn't handle transparency in an easy way, so transparent polygons need a separate traditional rendering path for them.

All in all, VT is interesting, but I wouldn't recommend it for everyone. It can work well, but it is hard to implement and optimize, plus there's just too many corner cases and case-specific tweaks needed for my taste. But for large open-world games or data visualization apps, it might be the only possible approach to fit all the content into the available hardware. With a lot of work, it can be made to run fairly efficiently even on limited hardware, like we can see in the PS3 and XBOX360 versions of id's Rage. 

Implementation

I have managed to get VT working on iOS with OpenGL-ES, to a certain degree. My implementation is not "shippable", but I could conceivably make it so if I wanted and had the resources. You can view the source code here, it might help getting a better idea of how the pieces fit together. Here's a video of a demo running on the iOS Sim. It looks very laggy because the simulator is terrible at emulating shaders, but it runs smoothly on a device.

The following diagram outlines the main components of the system in my implementation. It differs quite a bit from Sean's SVT demo (link down bellow), but it is closer in architecture to the one presented by the paper Accelerating Virtual Texturing Using CUDA, found in the first GPU Pro book (link bellow).




Page Files are the virtual textures, already cut into tiles (AKA pages) as a preprocessing step, so they are ready to be moved from disk into video memory whenever needed. A page file also contains the whole set of mipmaps, also called virtual mipmaps.
Page Cache Manager keeps an application-side representation of the Page Table and Page Indirection textures. Since moving a page from offline storage to memory is expensive, we need a cache to avoid reloading what is already available. This cache is a very simple Least Recently Used (LRU) cache. The cache is also the component responsible for keeping the physical textures up-to-date with its own local representation of the data.
The Page Provider is an async job queue that will fetch the pages needed for a given view of the scene and send them to the cache.
The Page Indirection texture is a texture with one pixel for each page/tile in the virtual texture, that will map the incoming UVs to the Page Table cache texture that has the actual texel data. This texture can get quite large, so it must use some compact format, like RGBA 8:8:8:8 or RGB 5:6:5.


But we are still missing a key piece here, and that's how to determine which pages must be loaded from storage into the cache and consequently into the Page Table. That's where the Feedback Pass and the Page Resolver enter.

The Feedback Pass is a pre-render of the view, with a custom shader and at a much lower resolution, that will write the ids of the required pages to the color framebuffer. That colorful patchwork of the cube and sphere above are actual page indexes encoded as an RGBA color. This pre-pass rendering is then read into main memory and processed by the Page Resolver to decode the page indexes and fire the new requests with the Page Provider.

After the Feedback pre-pass, the scene can be rendered normally with the VT lookup shaders. But note that we don't wait for new page request to finish, that would be terrible, because we'd simply block on synchronous file IO. The requests are asynchronous and might or might not be ready by the time the final view is rendered. If they are ready, sweet, but if not, we always keep a locked page of a low-res mipmap in the cache as a fallback, so we have some texture data in there to use, but it is going to be blurry.

Others resources worth checking out


The first book in the GPU Pro series. It has two very good articles on VT.
Mandatory paper by MrElusive: Software Virtual Textures.
The Crytek paper by Martin Mittring: Advanced Virtual Texture Topics.
And Sean's presentation on youtube, which I see you've already found. 


VT is still a somewhat hot topic on Computer Graphics, so there's tons of good material available, you should be able to find a lot more. If there's anything else I can add to this answer, please feel free to ask. I'm a bit rusty on the topic, haven't read much about it for the past year, but it is alway good for the memory to revisit stuff :)