Yup, the Google "Priority Inbox" feature does indeed use a linear classifier, in particular logistic regression [1] for the reason of scale as you point out.

Also, IIRC Gmail's original spam detection used naive bayes. It may have evolved since then.

[1] http://static.googleusercontent.com/media/research.google.co...