This is a pattern in Qt. In the Qt API, add appends at the end, and insert somewhere in the middle. Keep an eye out for it, you'll spot it everywhere it makes sense :-)
Ok, I solved inserting the "Help" menu too with insertMenu() instead of addMenu() so I get a QAction that I can use for all the menus I must insert before "Help".