ARP: As I told reapersaurus, most of those bonuses were from spells the cleric had cast. when the PCs are done beefing their weapons up, their around +15 or so as well.
Cleric: +5, Shock, Keen, Flaming Burst, Holy (+11)
Paladin: +5, Holy, Shocking, Keen, Flaming Burst, Holy venger (+11 or 12, depending on what you count Holy Avenger as)
The problem is persistent spell combiined with gloves of storing. You cast persistant weapon of the deity and persistant flame of faith, extended greater magic weapon, and extended keen edge on a sword that already has other enchantments, then slap it into a glove of storing so it is held in stasis. Now you've pretty much gotten +9 for free. And of course, the cleric stacks that with Assassin's Senses, while the Paladin uses Improved Critical, for some pretty hefty damage when they crit.
The party has just realized that you can get frost from a spell as well, so I'm sure they'll be hunting down someone who can cast Frost Weapon and be paying to have it cast as well. It'll only last for rounds rather than days, but that won't bother them much I bet.
EDIT: Wouldn't +16 be worth more than 500,000gp, considering it can't even be made with current magical technology?