I can reproduce it pretty consistently with my current session.

Every time the wrong tab gets restored, I get a bunch of
Unchecked lastError value: Error: ID already exists: [ID?]
errors from resource://gre/modules/ExtensionCommon.jsm:746
[ID?] is different for every error, and can be BA:48 or BA:6 or even MoreClosedTabs
Each of them have the same details:
withLastError resource://gre/modules/ExtensionCommon.jsm:746
create chrome://browser/content/child/ext-menus.js:148
I also get an uncaught exception: Object error in the end.

When the correct tab is restored, I only get the uncaught exception: Object error.

When I close a tab, I get this error (repeated 3 times as meant by the 3):

[Exception... "Component returned failure code: 0x80004005 (NS_ERROR_FAILURE) [nsIDOMWindowUtils.removeSheetUsingURIString]" nsresult: "0x80004005 (NS_ERROR_FAILURE)" location: "JS frame :: resource://gre/modules/ExtensionCommon.jsm :: runSafeSyncWithoutClone :: line 75" data: no] 3 ExtensionCommon.jsm:75:12
Details:
runSafeSyncWithoutClone resource://gre/modules/ExtensionCommon.jsm:75
cleanup resource://gre/modules/ExtensionContent.jsm:402
close resource://gre/modules/ExtensionContent.jsm:925
destroyed resource://gre/modules/ExtensionContent.jsm:1010
observe resource://gre/modules/ExtensionContent.jsm:1028

(In reply to Thomas Bertels from comment #1)

Every time the wrong tab gets restored, I get a bunch of
Unchecked lastError value: Error: ID already exists: [ID?]
errors from resource://gre/modules/ExtensionCommon.jsm:746

These IDs are created by my Add-on. They should not duplicate as they contain the session ID and per definition the session ID should be unique in this session.

After some searching, I've found this bug report:
https://bugzilla.mozilla.org/show_bug.cgi?id=1538119

In my opinion the problem behind this "random tab restore" is discussed more in detail there. Including a working testcase, a screencast and a suggestion on where this could be fixed in the Firefox source code.

So now we know why this happens and why it does not happen all the time and for everyone. Actually it is really easy to reproduce.

• Open a new Firefox session (be sure it is really new by unchecking "restore last session" in the Firefox settings and restarting Firefox once).
• Install my Add-on and open two random tabs.
• Close both tabs, right click on the toolbar icon created by my Add-on. There will be two entries for closed tabs.
• Now go to the Firefox preferences and check "restore last session"
• Close Firefox, reopen it
• Have a look at the context menu of my Add-on again. There should still be two entries.
• Now create two random tabs again and close them.
• Have a look at the context menu of my Add-on again. Still two entries when there should be four now and from this point on it may be possible that you don't restore the tab you think you would as the session IDs are duplicated now.

As the other bug report has better information, I'll mark this one as duplicate.