SE does indeed cache the toolbars of an addin. Each time you change the toolbar of your addin you should increase the GuiVersion. This is a property of the ISEAddin interface.
You might set the GuiVersion inside the Addin.OnConnection() method.
Another, but not recommended option for testing, is to reset the GuiVersion in the registry BEFORE starting SE the next time. If your addin was registered for Assembly environment in SE V20, you have to change the following key: