Thanks for the input, I know there are many opinions about url-rewriting. As I understand it then it does nothing for SEO but might increase the click-through rate since its easier for humans to recognize words in the url. Its also very helpful when sending links in emails. However the reason for installing it is not really relevant in regards to this problem. What it does is however very relevant.

Regarding installed modules. The same modules as were installed in version 1.3.8 are now installed in 1.5.1 (except the CEON URL module), however the updated version of the modules obviously.

I will consider turning off the CEON URL module to see if it makes a difference.