What SHOULD a sequence diagram show?

For most folks, a UML sequence diagram is something that is either (a) unnecessary, (b) clearly required and essential.  There is rarely a middle ground.  So when you create a diagram (whether by force or by choice) I'd like you to consider the audience, first and foremost.  What do you want to say to them?

Personally, I don't believe that it makes sense to create a diagram (of any kind) unless you are trying to communicate a thought that may not be clear any other way.  Diagrams are great for that, especially UML, because there is a rigorous way to create the diagram and a clear meaning for each of the symbols.

Therefore, first off, if you are going to create a sequence diagram, and you don't do this on a daily basis, brush up on the standard.  Look over the description in wikipedia or one of the many sites on the web.  (Ignore the agile sites... Many agilists don't have any fondness for modeling as anything more than Whiteboard Art and I've seen a few that play fast and loose with the diagram standards, which lowers the effectiveness of the communication).

But more important, try to consider this question: "who am I communicating with and what do they need to understand?" 

Let's say that you are trying to describe a scenario where five systems communicate in a distributed system flow.  Three of them communicate through sync calls to one another.  The other two communicate through async event notifications.

Why would you want to communicate anything at all?  Really.  You can describe things in text, right?  Well, what if the teams that will develop or update or maintain these systems are not familiar with async calls?  What if they've never done anything async before?

If that is the case, then you want to make sure that you illustrate the object lifelines.  You want to make sure that you show the "ACK" (aka "thank you") messages that go from an event notification to the event handler.  You want to show that the lifeline of the caller ENDS before the operations of the async partner is complete.  You want to show that a message is sent back to the collaborator at a later date with information about the processing and you want to make it clear if that return notification is async as well.

It's a lot to illustrate.  But the point is not to show messages moving.  It is to educate: what will the reader LEARN by reading your diagram?  What do they not already know? 

If you think like an educator, you often find that you remove excess detail, while clearly showing the things that you need the reader to understand. 

So, to answer the question, what should a sequence diagram show?  It should show the information that justifies its existence in the clearest possible manner, with a minimum of excess detail.