Is there a Safari shortcut that always works to reopen last-closed tab?
The answer is no, Safari does not provide any built-in functionality or shortcut (to the non-existing functionality) to restore the last closed tab.

The only functionality that Safari currently offers is:


Reopen last closed window
Undo Close Tab (as part of the Undo event chain) 


The first does just that, re-opens the last closed window, including all the tabs that were open when it closed.

The second works as you already know, it only works if it's the last thing you did, or you have to undo other things which is the caveat you noted above.

Looking at Safari Extensions, there are a few Tab managers around, however none of them specifically note their support for Tab Undo's except SafariTabs and this functionality was removed from the product for Safari 5; as the developer notes that Safari 5 now provides this as part of the Undo chain

Developing a solution for this while it's not trivial, isn't something that is going to be impossible as Apple have done most of the hard work. :D

Safari provides event propagation to Safari Extensions, and the particular one you would be interested in is CloseEvent (SafariEvent).  Of course determining a method of distinguishing between the CloseEvent's for Windows (with each Tab receiving its own CloseEvent) and singular Tab CloseEvents... well there's the hard work.