After some issues, I've correctly upgraded to magento 18.104.22.168
Now any users (customers and admin) can't anymore login in frontend or backend. They always get the "Invalid User Name or Password" error. Some days ago I've opened a question about the same problem that was marked as duplicate of this one. After some more investigation I can trustily say that it's not.
My current situation is that all the passwords saved before the upgrade from magento 1.6 to magento 1.9 are still registered with two character salt.
Despite from magento 1.8 the salt is made by 32 character, magento should still accepts old password.
In my case it doesn't happen and magento trigger the user/password error if the password has a two character salt.
Has I've described this is a totally different scenario from the one of the "duplicated" question (where 2 character salt are accepted but 32 character salt are not correctly created due to db misconfiguration).
I'm pretty sure the issue is due to the salt problem I've described and not relate to cache, cookie and so one. Customers registered after the upgrade have no problem and if I manually regenerate old pw with 32 character salt it works fine...
I really have no idea why my magento install works this way but I can't ask to thousands of clients to reset their passwords. After some days of thinking I'm still without any possible answer. I'll really appreciate any advice.