That's a great point. I think the term start-up should apply to high growth technology companies in the initial stages of their hockey stick curve (or which ever growth curve applies). Judging Foursquare on that basis, and assuming they can be as big as Twitter, they could still grow by about 15x, so indeed they might be in the early stages of their growth and could be considered a start-up.

However, valid criteria for classifying a company as a start-up might include: rounds of funding (# or type), number of employees, relative maturity (compared to industry peers), market share, culture or maturity of the firm's core technology.

It is indeed quite messy and hard to classify a company as a "start-up".