I'm not certain a PM feature would benefit this particular site with this particular community.
Right now the unavailability of PM creates a certain atmosphere. Everything you say has to be said publicly, to be rated or berated by the community.
So that's something special. Public communication being the only communication creates automatic policing -- prevents harassment of certain users (c'mon you know at least 10 nerds wrote marriage proposals in obfuscated C++ and planned to post them as comments..) and actually protects high rep usershigh rep users from private abuse and harassment except as they would otherwise receive from Jeff Atwood.
Do you really want people to be able to PM Mr. Skeet and be like
yo skeet... its dave.. i kno ur busy an all ..
I don't think so. Building messaging into the site has consequences -- namely that consequence that it will be used, appropropriately and inappropriately by certain parts of the user base.
Is it going to add or detract from the site? I think rolling it out as an experimental feature might be a good idea, but I'm not sure what its overall effect (+/-) will be to the communication that happens on the site.