Network Start Menu Causes Local to Disappear When Disconnected

I have a bizarre start menu issue to discuss. I've tried many fixes with no luck.

We use a network start menu combined with a local start menu. These work flawlessly in combination until someone decides to take a laptop home.

As soon as a user logs on a domain machine that is not currently connected to the network they receive an "empty" all programs on the start menu. All programs is populated if you navigate to Docs and Settings by hand, it just doesn't appear on the start menu. You also cannot right click the start button and tell it to "open all users". It's like they don't have access to the folder, but everyone can easily open anything they want if they navigate there through explorer. We're not dealing with high functioning users though so that's not really an option, even a start menu shortcut on the desktop scares the bajeezus out of them.

This only affects folks who have been added to a network users security group, which is under group policy and gives them a network start menu. Any domain account that is not in one of our user groups works fine on or off the network, but they don't have access to the network start menu at work.

I have attempted this with or without a roaming profile but the start menu still disappears with either scenario. Users that are outside of group policy have no problem with their local start menu, but they have 0 access to the network start menu when they are at work.

I tried the common fixes that are plastered all over the web. Shellfolders is correctly configured in the registry, the regsvr /i shell32.dll fix has no effect, and the folders are not hidden. The only method that works is replacing the network menu path in the registry with the local menu path... which isn't really a fix so much as a clue that it's probably stopping when it's unable to locate the network start menu.

I'm fairly certain this is somehow related to a failure to locate the network start menu, then stopping right then and there before applying the local one, I'm just not sure what can be done about it. Any crazy ideas would be greatly appreciated, we have 22 buildings and several hundred mobile machines that are plagued by this issue.