I think we want two solutions to this:
1. With a central server that does not need to be trusted (but can generate the shuffling.)
2. P2P version of poker. No need for servers (except maybe to find other players.)
I like option 1, too. Total decentralization is like the holy grail of online poker, but it seems to me that a central server would still be needed to organize the games, keep them moving along at a reasonable pace, and to act as a trusted escrow service to transfer funds back and forth. Maybe you could build a p2p client to handle all that, but then you'd get cheaters building their own clients to get around any constraints.
It's an interesting problem anyway and I'm pretty sure there is a big market for it. My own informal survey of bitcoin gaming sites tells me that the most profitable sites are also the 'provably fair' sites (bitZino, Just-Dice, etc). People aren't fools (for the most part). A provably fair HU poker site would almost certainly get a lot of action from high-rollers ... is my guess. I can see the $$ in their eyeballs now.
Physical Poker is popular because it is decentralised, you don't need to go to a casino to play, however, you are still depended on the dealer in your group being legit and that no one will run off with all the funds while you play.
A lot of these problems can be solved if using bitcoin as a payment method, using m-of-n transactions helps, but you'll still need a trusted dealer. Otherwise it'd just be like going to an unknown backstreet poker room and trusting that no one will rob you.