Magento rewrites and layered navigation

Question

I'm having a problem with a Magento shop. I'll explain it a bit:

Our shop has over 25k products. We use a lot of attributes because it's a fashion shop. (size, color, brand etc.) Our shop had over a thousend categories and was very slow because of so many categories, so we narrowed it down to 7 categories and added more attributes to help us filter.

The problem now however is the layered navigation. Let me show you an example:

When going to a category and selecting filters, the link is like this:

http://example.com/kinderkleding.html?doelgroep=jongenskleding&artikelgroep=broeken

The link that we want is: http://example.com/kinderkleding/jongenskleding/broeken.html

We have tried many different extentions like GoMage Layered Navigation and SEO Layered Navigation. The first one didn't work at all with this and the second one adds a "identifier" to the link. This means the link would be like this:

/kinderkleding/shopby/jongenskleding/broeken.html

So it adds "shopby" in the link. This is very bad for our SEO. We need the link without the "shopby".

We tried to rewrite our own links in Magento but that didn't work. We've got links like this with Magento rewrites: /kinderkleding/jongenskleding/broeken.html?doelgroep=jongenskleding&artikelgroep=broeken

Is there any way this can be fixed by an extension or custom php code? We've tried so many different things.

Is there anyone with a suggestion? I've made the last 2 links bold because I can't seem to be able to post more than 2 links.