Hello Torsen,
that is strange. Then the problem must be in something else, such as the URLs are not correctly generated in VirtueMart template or so.
But it is quite strange, that the URLs are non-seo both in menu and product browse page. That would mean the links are not generated correctly at both places.
However, if you are sure the fiters are gone and cannot cause the problem, even if I would gladly help you, I have really no more hints for you at the moment. (there have been similar sonding cases as yours, but it was always fixed by filter adjustments or cleaning cache so far)
If it would be just menu non-making SEF URLs, I would guess it is wrong menu module code, that generates links in wrong way (there has been such modules available at RocketThemes)
If it would be just category browse page, it could be some problem in VM template.
The combination of both is also possible, but no so likely.
If you would provide us with access codes to your site, we could try to check the situation. But in case, the problem would be caused by error in template, 3rd party component or incorrect configuration, we would charge you for the service.