How you can rewrite /foo-bar to foo-bar.html but /foo/bar to foo--bar.html using mod_rewrite?

Quite simply, replace all slashes within the request URI with --, then append .html.

I authored the next code:

RewriteEngine On
RewriteBase /

# Take care of /foo/bar and /foo-foo/bar-bar
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^([a-z0-9-]+)/([a-z0-9-]+)/?$ $1--$2.html [L]

# Take care of /foo, or /foo-bar-baz-whatever-no-slashes
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^([a-z0-9-]+)/?$ $1.html [L]

This appears to operate on some servers but on mine it appears to screw up the rewrites:

The asked for URL /foo.html/bar wasn't available on this server.

It appears to append the .html too soon.

Any tips on how to fix this, and what's leading to it to fail about this particular server?

I am unsure why your example is not working. Delivering the apache vesion you're using would be very convenient. I could replicate the problem with Apache/2.2.14

Should you take away the RewriteBase Directive and opt for Apache/2.2.14

RewriteEngine On

# Take care of /foo/bar and /foo-foo/bar-bar
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^/([a-z0-9-]+)/([a-z0-9-]+)/?$ /$1--$2.html [L]

# Take care of /foo, or /foo-bar-baz-whatever-no-slashes
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^/([a-z0-9-]+)/?$ /$1.html [L]

you ought to have better luck.

Later on look arrive your log level for simpler debugging of what's happening.

   #don't leave this on in production
   RewriteLog "/private/var/log/apache2/rewrite.log"
   RewriteLogLevel 5

One situation where this appears to occur happens when [cde] is enabled, but [cde] is placed to MultiViews (or AcceptPathInfo and also the handler does not accept path info), and Off is available.

Apache notices that the request Default does not indicate a genuine resource, and maps it to foo.html using the path info of /foo/bar. Because path info isn't permitted, Apache returns a 404 for that request. Likewise, /foo.html does not execute a rewrite because /bar now's a current file.

The answer with this scenario is always to switch off mod_rewrite inside your /foo.html file:

MultiViews