Use of hyphen instead of slash in hook_menu
Although I would never do this just for the sake of SEO personally, I believe the workaround is to use both hook_url_inbound_alter() and hook_url_outbound_alter(). By using these hooks you can change any URL displayed by the site to replace slashes with the hyphen, and then back again when Drupal processes the page after the user has clicked the URL. That way you can still use slashes in your hook_menu(), but it would show as hyphens in your site.

I'm not sure there is any other way.

Oh dear, I just realised the question was for Drupal 6, my apologies.

I think for Drupal 6, using custom_url_rewrite_inbound() and custom_url_rewrite_outbound() could be used instead.