That really is a nice question, although once you're Facebook or Google etc., you have the opposite problem: how to reduce the number of features from many billions, to let's say, a billion or so.
There really are billions of features out there.
Imagine, that in your feature vector you have billions of possible phrases that the user could type in into search engine. Or, that you have billions of web sites a user could visit. Or millions of locations from which a user could log in to the system. Or billions of mail accounts a user could send mails to or receive mails from.
Or, to swich a bit to social networking site-like problem. Imagine that in your feature vector you have billions of users which a particular user could either know or be in some degree of separation from. You can add billions of links that user could post in his SNS feed, or millions of pages a user could 'like' (or do whatever the SNS allows him to do).
Similar problems may be found in many domains from voice and image recognition, to various branches of biology, chemistry etc. I like your question, because it's a good starting point to dive into the problems of dealing with the abundance of features. Good luck in exploring this area!
UPDATE due to your comment:
Using features other than binary is just one step further in imagining things. You could somehow cluster the searches, and count frequencies of searches for a particular cluster.
In a SNS setting you could build a vector of relations between users defined as degree of separation instead of a mere binary feature of being or not being friends.
Imagine logs that global corporations are holding on millions of their users. There's a whole lot of stuff that can be measured in a more detailed way than binary.
Things become even more complicated once we're considering an online setting. In such a case you do not have time for complicated computations and you're often left with binary features since they are cheaper.
And no, I am not saying, that the problem becomes tractable once it's reduced to a magical number of billion features. I am only saying that a billion of features is something you may end up after a lot of effort in reducing the number of dimensions.
