Yes, the control keys are set correctly. In fact they work great when I use EditUrl("controlkey").
To use the code from your tutorial as an example, what I am seeing is that:
Response.Redirect(Globals.NavigateURL(PortalSettings.ActiveTab.TabID, "mygallery", "mid=" & Cstr(ModuleID)))
will take me the control w/ key "mygallery", but
Response.Redirect(Globals.NavigateURL("mygallery"))
takes me to a blank page that doesn't contain my control.
It is clear from looking at the NavigateURL source that the "mid=" part is not added in like when you use EditUrl. I am curious though to know what the intended behavior is for the NavigateURL(ByVal TabID As Integer) method, because it doesn't work for me as expected.