I commented on another answer that the problem is that when resolving the items, the incoming has the reverse replacements applied. Since you have 2 replacements both mapping to "-" then on incoming it fails since it tries to replace "-" with space initially, but some of those hyphens should be underscore but it has no idea which one should be which.
For example, given path: /path to some/item_url
then the generated url is /path-to-some/item-url
.
On incoming, the reverse replacements are replied, and Sitecore is now looking for /path to some/item url
, which does not exists and so a 404 is thrown. Since the "_" (underscore) was replaced by a "-" (hyphen), on incoming the "-" (hyphen) is replaced with " " (space). Since there are no hyphens left to replace, it cannot replace with underscore.
Take a look in Sitecore.Pipelines.HttpRequest.ItemResolver, Sitecore.Kernel
and you will see a call to MainUtil.DecodeName(args.Url.ItemPath)
where the EncodeNameReplacements are applied.
You are better using an event handler to deal with these in the first place so you don't then need worry about any kind of mapping.