The best answer that I have come up with is as follows:
- Not to save the files in
personal.xlb
but to save them in an AddIn (an .xlam file) - To add the menus to the Addin via Custom UI Editor For Microsoft Office (downloadable from http://openxmldeveloper.org/blog/b/openxmldeveloper/archive/2009/08/07/7293.aspx)
- To save the file in the "Shared With Everyone" folder of "SkyDrive Pro"
- To send a link to the file to my colleagues
This seems to solve all the issues. If I do an update then it seems that if my colleagues restart their computer then the addin is updated automatically.