sorting - batch-rename filenames with numbers to sort alphabetically

I want to batch-rename files containing numbers, padding the numbers with zeroes.
The goal is to sort numbered sets of files alphabetically in the correct order in any application.

In a set of files with the same prefix text followed by a number, I want to pad each number with as many zeroes as the highest number has digits.

I.e a list of files named like this:

xx 1 abc.txt
xx 2 def.txt
xx 3 ghi.txt
xx 3.5 jkl.txt
xx 4a mno.txt
xx 4b pqr.txt
...
xx 100 end.txt

should become:

xx 001 abc.txt
xx 002 def.txt
xx 003 ghi.txt
xx 003.5 jkl.txt
xx 004a mno.txt
xx 004b pqr.txt
...
xx 100 end.txt

(System is Windows XP)

(Windows Explorer uses some kind of heuristic to sort files with numbers in this way, not always correctly. I am however looking for a way to actually rename the files)

Addendum

I was refered to this question as a possible duplicate:
How can I mass rename files?
The tools mentioned there (Bulk Rename Utility, AntRenamer, Free Commander Portable etc.) are as far as I can tell not capable of detecting the minimum amount of paddding needed for each set of files.

My thinking was this: Explorer is capable of detecting files with consecutive numbers, even if they are left-aligned without padding, as in my first example above. It uses this detection in order to sort the files correctly.
(see for example http://www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html )
I am looking for a tool that does the same detection, but also renames the files accordingly.
(Finding the largest number for each related set of files, not simple the largest number in the whole directory, and then padding the numbers in each set.)

Or to put it annother way: I want to do a "natural sort" for all files in a directory, then rename them so that the ascii sort is identical to the "natural sort"

I now suspect that there is no tool capable of doing this, so I probably just need to write a script.