How bad does the service have to be to justifiably leave no tip at all?
I would say it has to be pretty bad. In particular, the server would have to have been willfully refusing to accommodate some request or other. If the service were just inattentive, I would probably just leave a smaller tip.
In most cases I'll leave slightly less than 15% if I'm unhappy with the server. (I find it unfair to penalize the server for bad service that is the fault of management or other circumstances beyond his or her control.) If I were very unhappy, I might go down to 10% or 5%, depending on the size of the bill.
Some servers find a minimal tip more insulting than no tip at all, so if I were really upset I might leave a dollar or a handful of pennies. I should emphasize that this is exceedingly rare. This probably happens less frequently than once every ten years, even though I am often very critical of restaurant service in the US. Even leaving slightly less than 15% probably happens once a year or less.
I also learned a trick from a friend of mine: if something is upsetting you about the service, the best way to deal with it may be to say something about it to the server in a fairly neutral way. That is, do not sound like you're complaining or protesting, but telling the server how you like to be served (for example, "please don't clear the table until everyone is done eating"). A little communication goes a long way.