It's true, wp-list-categories is NOT a good Navigation menu for your site. I agree with that for my site also.
For some of my sites I wanted to make a Navigation that has some Pages, some Categories, and maybe an Offsite link, or link to a non-wordpress part of your domain.
It is possible to make your nav links by-hand, instead of a Template Tag or "call" that lists everything -- be it all your Pages, or all your Cats.
@diad If I understand correctly, it sounds like basically you are using the Pages function to set up a nav menu with wp-list-pages, and each Page links you to a Category that you want in your nav. Is that how you're workin' it?
WP is pretty flexible, there's a lot of ways to do it, I have not tried that way.