I think I've found some kind of issue, and while I'm not sure about the root causes, this workaround seems to fix it.
First, I have to say I'm using this plugin on other installations with other (similar) plugin configurations and it works great.
But for some reason, during my last installation I noticed that some posts and pages would lead to 404 errors. I analyzed the kind of posts and pages that were causing the issue, and all of them seemed to have a revision saved. I could see this revision listed in Tools > Custom Permalinks with the same custom permalink as the defined for the original post.
Posts / pages with no revisions or custom permalinks defined were working perfectly. So I decided to erase all revisions (using Better Delete Revision) and give it a try again. After all revisions were erased, the custom permalinks worked perfectly once more!
Again, I don't know what this is happening on this particular installation (it works great on other ones) but removing the revisions seemed to fix the problem.
However, this was just a quick workaround. I needed to keep revisions working, as autosaves and updates were still generating new revisions and thus breaking the custom permalinks, leading again to 404 errors.
So my guess is that the custom permalinks plugin was querying the database to find out the original URL related to that post, and returning the URL of a post revision, which wouldn't work.
I tried removing potential matches from revisions that seemed to break how this was working by editing the original plugin code. After line 164 of the custom permalinks plugin php file, inside custom_permalinks_request, I just added this code to the query:
" post_type NOT IN ('revision') AND ".
Filtering out results from "revisions" seemed to fix it. And all the 404 errors stopped appearing. Does all this make any sense?