URL Encoding with Underscores in a Directory Name?

You should not encode the directory names as you create them (as you suggested). Encoding should only happen at the last stage where it is handed out to the browser. That's why you are ending up with 'double' encoding: %25 is % and 5F is the leftover from the first encoding of underscore.

Also, note that you don't need to encode underscores according to rfc1738.

2.2. URL Character Encoding Issues

...

Thus, only alphanumerics, the special characters "$-_.+!*'(),", and reserved characters used for their reserved purposes may be used unencoded within a URL.

There is double encoding happening in what you are showing. Two steps should be enough:

andy_test is both the string in the software and the actual name of the directory or script in the filesystem (the resource the web server accesses)

andy%5Ftest is andy_test URL encoded. This string should the browser use (it's not really needed in the underscore case, but may be in other cases).

andy%255ftest is just andy_test URL encoded twice, which makes no sense, there should be no need to. Just decide WHERE you will do the encoding. If you do it both at the code level and at the webserver level this is what can happen and the result is broken links unless you are decoding two times again, which is not really needed nor sane.