I have to wonder if a person with thousands of followers would be willing to risk their online social clout for a product. I also wonder what level of effectiveness it would have. I tend to ignore most (not all) of those people because it's pretty clear to me they are busy gathering followers to impress someone. The few that I do pay attention to are unlikely to become a spokesperson for you - they have a solid online reputation and aren't going to tarnish it.
Twitter is no more "pure" than anything else. You can go to any freelancer site and buy tweets, facebook likes or endorsements, or whatever...not my cup of tea, but I've checked it out.
On the higher end you can buy tweets from celebrities. There are even ad networks for them. Google: 'Celebs Paid to Tweet About Products'10K+ per tweet. (They are supposed to disclose their ad tweets.)
Sometimes when I send out a tweet I get a mention for some product or website. I often block the Twitterer or report it as spam. It just isn't worth going all through the trouble only to have people ignore it.
Like someone said earlier, there are few established sponsored tweet networks out there which act as a platform for connecting tweeple with advertisers. Simple Google search for sponsored tweets can land you on some of those networks.
There is mandatory disclosure policy for such tweets with hashtags like #spon or #ad , etc.
The rates can vary from single digit to upwards of 4 digits for a single tweet.
I've paid for people to tweet stuff before, in all cases it wasn't worth the spend. Of course, I could pay Kim Kardashian $10,000 to tweet something and probably get better results, but the problem is that most of the non-celebs "selling" tweets don't have real followers, they were purchased. So naturally your ad money isn't going to get a large response, if any at all, because people aren't "really" following the person you're paying to promote your link.