If you ever lose the toolbar, run the Outlook configuration wizard--go to start/programs/Microsoft CRM 4.0/configuration wizard.
If you are off-line state, you probably will lose whatever changes were made since you last went on-line.
You can also try going to the trust center, disabling the CRM add-in, restarting Outlook, go enable the add-in, then restart Outlook. That may do it.