I think that the "one try only, willing or unwilling" interpretation of the revivification against one's will rule is an incredibly twisted one, given the example on PHB p.153. That aside, there are a number of ways to kill off characters (semi-)permanently:
1) Soul bind (no resurrection possible, even via wish or miracle). This spell works wonderfully in conjunction with sequester cast on the gem, or simply by giving the gem to a demon lord or evil deity or feeding it to the tarrasque.
2) Trap the soul. Same deal, and IIRC, there are some monsters (the devourer and demilich) who can eat the trapped soul at their leisure.
3) The blazefire ability of the winter wight and lavawight. The hit point loss caused by this ability simply cannot be regained by any means. IOW, a character killed by physical damage by one of these creatures has no way of rising above -10 hp, and therefore no way of being alive.
4) Animation as an undead creature. They have to kill you before you can be resurrected, and presumably, the bad guy has you somewhere very hard to find.
5) Spheres of annihilation.
6) Bag of holding + portable hole. A living being (or soul gem) cast into the vortex created by this evil combo is "lost forever."
7 - infinity) Any number of artifacts, circumstances, and creatures the DM's mind chooses to originate.
Pcat raises a good point as well. True, the PCs might be smart and well-connected enough to have arrangements with other high-level folk under which those folk will search them out and resurrect them if they're missing for longer than x days or weeks. How many PC parties do you know who actually do this? My PCs (EPL 21) don't, and they go wandering across their homeworld and other planes at a whim. If they fall as a group, no way in Hades are they being tracked down and brought back. Hell, even their allies don't expect to be able to scry for them, what with their constant mind blank protections.