Arthur,
Definitely something strange is going on. It sounds like Joomla's database tables may just be corrupted in some way, and that's not something that's easy to deal with.
While I've never used it, you may want to look into
ACL Manager
. It is a commercial extension, but one of the things it can do is fix bad data in the underlying tables of Joomla. It's main purpose is to simplify the creation of ACL rules in general and make things much easier.
Again, I've never used it, but I've heard great things and other users with similar (though not the same) type of issues have mentioned that that extension has fixed it for them. Depending on how developed your site is, or whether you can start over/spend time to debug everything, the investment in that extension may be worth it.
Hope that helps, but definitely keep us posted on what you find. Curious to hear a solution. Of course, if there's anything else you think we can do, just let us know.
Thanks,
Alex