From personal experience with QCII paging on a P25 Phase II system (TDMA talkgroups) with APX subscribers decoding those tones (Tone Signaling feature), they are every bit as reliable as analog paging being decoded with Minitors. The tones are generated in the subscriber by the AMBE+2 vocoder, so you wind up with a faithful reproduction. Of course it helps when the tones are being encoded by MCC 7500 consoles. If you try the same with a tone encoder designed for analog modulation, well then good luck. But to say that tone paging over digital is a "nightmare" is simply not accurate.
The key is having the AMBE+2 vocoder in the sending radio. We're doing tone paging over P25 Phase I using Harris XG75M control stations and Zetron Max consoles. The outgoing tones sound good and clean, and it sounds pretty clean at the receiving end for a variety of radios, including old M7100/P7100 and XTS/XTL stuff; even sounds reasonably decent from a scanner.
However, sending tones with anything older (Harris M7100, Moto XTL, etc) and you might as well forget it. Most tones will sound nasty.
Of course, the only radios we can decode with are those properly equipped for P25 paging. It's mainly moot since the tones are also going out over the analog paging channel, which is the primary alert channel. Paging over P25 is there in case any agency wants to implement Unication G4 or G4 pagers (with which it works great).