I've done it. Algorithm::FastPermute.
It can comfortably print all the permutations of ten elements in less than a minute, on my iBook. So it's almost four times as fast as Algorithm::Permute.
Update: Email to firstname.lastname@example.org and email@example.com is bouncing. Does anyone have his current email address?