Issue with menu caching in Drupal 6
Your idea to rebuild the menu cache on each login would certainly be resource intensive, but it would moreso just not work either as the cache is system wide and isn't somehow custom cached across page loads of a user, so, once someone logged in, it would be rebuilt and then accessible to both that as well as any other currently logged in user.  Then, when the next user logged in, it would be rebuilt for all to use by everyone logged in, etc etc etc.

But, you could rather easily as you intimated do this with php inside a new page callback, eg, something along the lines of...

if ( /* users we are looking for is TRUE */ ) {
  // use our new callback
} else {
  // call original callback
}


By doing it inside the callback, you wouldn't be duplicating menu paths, eg, not having module/callback1 and module/callback2 but rather module/callback in itself would do things differently based upon your new logic...much like how going to user as an anonymous user presents a login page, but going to it once logged in presents your profile.

ADDITION:

Given additional commentary, you most probably could overload/overuse the capabilities of hook_translated_menu_link_alter() to accomplish this, eg, something like:

function YOURMODULE_menu_link_alter(&amp;$item, $menu) {

  if ( /* whatever is true for your $item */ ) {
    $item['options']['alter']=TRUE; // Flag this link as needing an alter at display/run time.
  }

}


and then

function YOURMODULE_translated_menu_link_alter(&amp;$item) {

  if ( /* whatever is true for your $item */ ) {

    // do whatever you want to do to it, eg...

    if ( /* this is a special user */ ) {
      $item['localized_options']['attributes']['class']='foo';
    }

  }

}