Hi guys,
I see no one participated to this thread, which is a shame, but I did some research and, even though I'm not sure I got a totally conclusive answer, I have some information that I think is useful to share, just in case someone stumbles upon my same problem and needs help with it.
Through his blog, in the comments to the article that points out the issue of *poor* permalinks strings and performance, Otto kind of answered my question.
Essentially the Custom (permalink) Structure (where you can type the string of your choice) apparently applies ONLY to posts, therefore pages, if you have rewrite ON, will always be named according to the title of the page in the URL, like domain.com/name-of-page/. The problem seems to be that if you have a bad structure (only %postname% for instance) WordPress will struggle to differentiate between posts and pages and will start adding lots of internal 'notes' to the Data Base (in particular the wp-options table in the rewrite_rules record).
So, if you have a website made of lots of pages and a BAD permalink string, the problem starts to increase the bigger the website becomes. If you use a good permalink structure (which eliminates any doubt about what that URL refers to (like /%post_id%/%postname%/) even if this applies only to posts - and not pages - this is sufficient to scale up the website quite considerably without problems.
This is that I understood by reading a couple of articles and most comments underneath. Hope this helps someone because performance is crucial. Slow websites turn users away.
** Of course, it's still to be understood for me if it's a good thing that the engine looks through the DataBase following alphabetical indexes as opposed to numerical ones (e.g. title-of-my-page) but I like to use pages for non time sensitive data, and I like the idea of making small sites with WordPress, so I guess I'll stick to it as far as the DataBase doesn't get bloated because of lots of rubbish **.
Cheers!