When the traditional way to destroy coins has always been sending them to an random address it is very interesting that they had some need to do something else. The only reason I think it has been done this way with the fees is that their nature is such that they are physically incapable of doing anything right.
If they sent them to an address with no private key, people who don't understand cryptography would accuse them of secretly knowing the private key. Of course, then the coins would be sitting at an (inaccessible) address so people who were suspicious could watch them and check that they don't move, which of course would never happen because there really is no private key.
The way they burned them makes it even more clear, because the coins literally do not exist anywhere on the blockchain any more, and if they don't exist on the blockchain they don't exist, period. But then people who don't understand blockchains accuse them of being able to recover the coins somehow later, even though that's impossible. Peercoin burns transaction fees, and paycoin is a peercoin clone + hyper-inflation.
They created the PR problem by (1) doing the "testing" on the live network, (2) waiting two months to respond, (3) moving the coins and mingling them with other coins, (4) promising not delivering an analysis of how many coins needed to be destroyed, (5) ignoring the fact that a much larger number of coins need to be destroyed from the hyper-inflationary stakers, and (6) having a history of shady behavior so that every non-transparent thing they do just raises more questions. I'm being generous in that list, because it seems more likely that JG, not understanding blockchains, thought that if he just waited a couple of months people would forget about those "test" coins and he could sell them to try to pay the bills.
But my original point is that the coins are verifiably destroyed. They don't exist anywhere on the blockchain, and because of how blockchains work there is no way to recover them.