How I define a startup:

In my mind, startup-ness is not about size, but about culture. You've got invaders and you've got occupiers. Invaders have to improvise, have to be agile, have to seek out a better way because they have no incentive to uphold the status quo. Occupiers just keep doing what they already do, optimizing it perhaps, but never truly innovating. There are 40-person companies out there who've already become occupiers, and there is one 400 billion dollar giant who is arguably still in invasion mode.

I also like Eric Ries' definition: a group of people operating under conditions of extreme uncertainty.