Hi amadecs, no SEO mod does everything that you're listing, there are several items that are separate issues.
#1. XC SEO is good on performance, and is not encrypted, so you have full access to the source code (it's licensed as Open Source, GPL)
#2. XC SEO, DSEFU both dynamically rewrite urls on the fly. DSEFU is pretty much the same as XC SEO, except it costs money.
#3. CDSEO will convert your urls initially, but there's no automatic conversion after that initial conversion. Additionally, while the urls are totally customizable, you can't customize the url generation in an automated fashion without having to hire the author or another PHP developer.
If you want to be able to change URL structure and still have urls dynamically generated, I recommend XC SEO, as you can make the changes yourself (if you're savvy enough) or ask for help in the forums, or ask a PHP dev. XC SEO already allows you to inject your own custom word or phrase into urls. And since the code is open source, you can change the method for separating the words in the URL, via the PHP class (and also in the .htaccess file)
Regarding the page title structure, you can change that, but you should search the forums, as there are free solutions from other users on that matter.
For page titles & metadata, that will also require separate customization, and there are free (and cheap) solutions for that around the forums as well.
Some additional notes:
#1. CDSEO is probably the most powerful solution, in terms of manual control over each url, but is also the slowest.
#2. DSEFU and XC SEO rewrite pretty much all desired sections of X-Cart in their base package, CDSEO rewrites Categories and Products and requires the purchase of addons for sections such as Static Pages
#3. DSEFU's feature list is here:
http://www.safetynetweb.com/Dynamic-Search-Engine-Friendly-URLs-pr-1.html << Since DSEFU and XC SEO are so similar, they have pretty much the same feature list
The reason for the similar feature list with DSEFU and XC SEO, is that when I came to X-Cart, I found the only SEO solution that I saw at the time was DSEFU. It wasn't free, and required many manual edits, and wasn't feature complete (imho). I released XC SEO as a free alternative with more features, solving the shortcomings of DSEFU. Since then, since DSEFU is a commercial product, they've made sure that they at least meet the feature list of XC SEO, if not surpassing in one area or another.
The points against DSEFU are:
#1. Encrypted source code
#2. Not free
The points against CDSEO are:
#1. Encrypted source code
#2. Not free
#3. Slowest solution available
The points against XC SEO are:
#1. There may be bugs that still linger in the code. I know there are bugs in the competition software, but since they are commercial packages, you get solutions to the bugs. If you use XC SEO and find a bug, you have to rely on another user or myself fixing the issue, and there's no guarantee on turnaround time
Good luck in your decision. If you have an unlimited budget, you can probably find what you need with CDSEO + additional customization from the author to make the module dynamic, same for DSEFU.
Cheers!