It's certainly an interesting problem ... much trickier than I first imagined. Even though 'provably fair shuffling' != provably fair, I agree that the feature is still worth implementing. Rumors are running rampant that the shuffling algorithm on Pokerstars is rigged to favor the weaker players. See http://www.pokerscout.com/AllReviews.aspx?id=1 , and the general mood seems to be that most of these poker sites are crooked as a barrel of snakes. This would at least help to build back some trust.

I like your idea though, and I recall that libertaad wrote some excellent aricles on 'provably fair' not so long ago which I need to go back and re-read. I'll give the subject some more thought and see what I can come up with.