> When was the last major update where buttons got re-added?

Not so much re-added as just added. The download button (arrow) for example was added in Firefox 20.

Add-ons also tend to insert their buttons. Or even reactivate the add-ons bar. But it takes seconds to fix.

Firefox 4-20 hasn't had any toolbar button changes. You really can't count third-party addons as something that Mozilla changes to the toolbar.