How to build a dynamic menu structure
I found a way to do this, but I'm still interested to know if this is the right approach (and if bad things will happen with a very large number of groups and users).

Both menus are created using hook_enable in the install file of the module (the development module is an excellent example on how to do this). 

Like I say in my comment, I don't think you can create dynamic menu items so I'm creating a menu item for each group (when a group is added, I need to do a menu_rebuild). To determine if the menu item should be visible for a user, I created an access callback that checks if a user is part of that group. This callback will be called with every page request, so it will always work.

The secondary menu works with a wildcard and a to_arg function. For example, a menu item is set as $items['pmenu/%get_groupid/grouppage'] and in the function get_groupid_to_arg($arg) I'm extracting the groupid from the path with arg(1), which is returned (for details see hook_menu and the Menu example). The secondary menu items also use the same access callback to check if the user may see the menu item.

Finally I had to apply a fix for the theme, because the corresponding primary or parent menu item (group) would not be set as active if a secondary menu item was selected. I'm using Marinelli and applied the patch in comment 14 of this issue. That didn't quite work, so I changed it a bit to only look at the path when checking for a parent as described in comment 16.