You can't solve duplicate content issues with a sitemap. That only tells search engines what content you have, that you want search engines to find for sure. Search engines also just browse your site to find content that isn't in your sitemap.
So on monday they go to /shoes/brown/brand/supershoes.html and on tuesday they could follow a different path /brand/shoes/brown/supershoes.html which will bring them to the same content on a different url.
The only way to counter this is by the use of the rel=canonical. Or, use a noindex on the dupe's.
Putting the non-vanity url in the sitemap will add another url in the index. The non vanity, the vanity, the dupe's. So you'll be adding more junk to the system.
I wouldn't worry too much on the duplicate content issue. Yes it's a pain in the ass, yes it should be easy to solve. But the only thing which really happens right now, is that Google might not display your preferred url in the SERP's right now. As long as you're not jacking content from another site and posting it on your own site, you're in the clear. Oh and yes people might link to the "wrong" url.
If you can't solve it with the rel or the noindex in the header within a reasonable time. Move on to other stuff! Handle with this issue once you change to another CMS and do a proper redirection effort.