Or use some sort of a freemium model much like the one they ended up doing anyway.
So Gaga and Obama should actually be charged an annual fee of something like $20,000. Maybe it's tiered, so someone like Robert Scoble pays $2,000.
Going by number of followers, Gaga's influence is an entire order of magnitude higher than Scoble's, so it makes sense for her fee to be an order of magnitude higher.
Everyone else below a certain threshold is free. I wouldn't (and shouldn't) pay for Twitter...it gives me little influence.