Linkedin has sort of tried this w/ premium accounts. 3 InMails for $20/mo. Not sure if premium accounts are really driving their revenue as much as recruiter solutions.
Worth noting that "InMail" credits aren't the only benefit of a LinkedIn premium account, and in fact of people I know with paid accounts very few of them care about this particular aspect.
http://press.linkedin.com/node/1223