What do we hook in Drupal 6 for inbound URL rewrites? Where conditional rewrite is desired, not supported by existing path modules, and where we'd prefer to stay out of .htaccess, where might we hook in Drupal 6?

Along the lines of Drupal 7 hook_URL_inbound_alter, I think.
hook_URL_inbound_alter was introduced as part of a contributed module in Drupal 6 (URL alter), and was moved to core with Drupal 7.