Ask HN: Who's the most important person you've emailed and answered?
President? Big Shot CEO?, the Pope?
Yes, I've emailed and had responses from people matching all of those categories. (A sample includes Eric Schmidt, Jennifer Tilly, John Conway, Randal Schwartz, Paul Graham, Ann Curry, and Laurie Garrett.) Many of them remember me in turn. Several are in my phone. I've met people like this in many different ways, for many different reasons.
My advice is not to bug famous people simply because they are famous. But if you have a legitimate reason to contact someone, don't shy away because that person is well known in some circle.
Also remember that all fame is local. Some people know about the fame and are impressed. Others don't realize the person is famous and don't care. At the end of the day they are people like any other. But frequently busy, with many people trying to get a slice of their time. Most famous people don't like people fawning over them. (You don't want to know the exceptions. Really.) So if you do find yourself taking a slice of their time, get to the point quickly and stop there.
There was no response until 1996, when he replied that a paperback had recently been published, wrapped in one of the worst covers he had seen in his entire career.
John Graham Cumming (http://news.ycombinator.com/user?id=jgrahamc) beats me by many lengths though: http://blog.jgc.org/2009/09/hello-john-its-gordon-brown.html
Needless to say, it made my semester (and not only because I got 20% extra credit on an assignment where that wasn't an option).
(If Usenet counts, Bjarne Stroustrup)
(Of course, it's self-reinforcing. People know ESR by his initials because that's how other people refer to him, and you can refer to him by his initials because people will know who you're talking about.)