Pretty URLs with Pagination

(Here I go again...)

I'm finishing to setup my site and hacking htaccess file to redirect the long dynamic search URLs. But I stopped progression because search parameters for categories.

I'm using the recommended Pagination for Static Pages (http://www.movabletype.org/documentation/designer/pagination-static.html) technique for Main Index Page and Category Archive Listing Page. For the Main Page, things went smoothly:

Default URL: www.mysite.com/cgi-bin/mt-search.cgi?IncludeBlogs=XXX&template_id=YYY&archive_type=Index&page=ZZZ

Pretty URL: www.mysite.com/archive/pageZZZ

But with the Category Archive, I stopped here:

Default URL: www.mysite.com/cgi-bin/mt-search.cgi?IncludeBlogs=XXX&template_id=YYY&archive_type=Category&category=ZZZ&page=AAA

Pretty URL: www.mysite.com/category-ZZZ/pageAAA

The problem here is all XXX YYY ZZZ and AAA are numbers. Categories can be named on MT. Why mt-search.cgi can't accept names instead of numbers? I'm not saying search for a Category named like this "Some Whack a lot Named Hyper Category Made to ME!" but for its folder, which MT created and encoded for web use. Like this:

Default URL: www.mysite.com/(...)&category=proper-named-folder&(...)

Pretty URL: www.mysite.com/proper-named-folder

Does anyone know if there's a plugin that modifies the search behavior to accept this query?