Hey WebFreak - we're in the thousands. We've been in the hosting business (publicly) since 1998. We've been doing this since 1994 however, but back then it was only for web design clients that we designed sites for. What's nice about our particular company is that most of our customers have more than one hosting account - many with 4 or 5 packages each. Due to this, customer retention is very important as losing ONE customer means losing multiple accounts (and their referrals).
We're almost 90% referral based business. We have run a few advertising campaigns in the past, but it's our customers that tell others about us which helps our business grow.