toString(): for debugging or for humans?

Would you format an address the same way in a SMS message and in an HTML page? Would you format it the same way in English, French and Japanese?

If no, then you have your answer : the presentation does not belong to the object, but to the presentation layer displaying the object. Unless the object is specifically made up for the presentation layer, for example if it is a HtmlI18nedAddress, use toString for debugging.

Consider Date vs SimpleDateFormat. Date contains the state and SimpleDateFormat returns multiple representations.

I would say the first. Data formatting should not be hard coded into the ToString() function of the object.

I look at it this way: I try to make my ToString() output data that is readable by a matching Parse(string data) function (if that function actually exists or not is not important). So in this case, if you want a specific formatting, write a specific function, and leave the generic data dump routines to ToString().