If you really want padding, you could do this with multiple rules, matching various lengths
RewriteRule ^/product_images/(.{1})(.{4})/(.*)$ new_product_images/000$1/$2/$3
RewriteRule ^/product_images/(.{2})(.{4})/(.*)$ new_product_images/00$1/$2/$3
RewriteRule ^/product_images/(.{3})(.{4})/(.*)$ new_product_images/0$1/$2/$3
RewriteRule ^/product_images/(.{4})(.{4})/(.*)$ new_product_images/$1/$2/$3
Or, just have your folders be 1 or 2 or 3 characters (no padding) and use 1 rule for everything.
RewriteRule ^/product_images/(.+)(.{4})/(.*)$ new_product_images/$1/$2/$3
This would map
- 12345 -> /1/2345
- 123456 -> /12/3456
- 1234567 -> /123/4567
- 12345678 -> /1234/5678
This doesn't keep the folders in order, but its a simpler rule.
You could also use a fixed length prefix - for example, anything that starts with a single digit is in a different folder. Here's an example with 2 digits
This would map
- 123 -> /12/3
- 12345 -> /12/345
- 123456 -> /12/3456
- 234567 -> /23/4567
- 2345678 -> /23/45678
Using this, 2 characters cuts your problem by a factor of 100.
The only problem is IDs less than 100 - one solution might be to leave those in the existing folder (product_images), and your RewriteRule only applies to IDs 100+.
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^/product_images/(..)(.+)/(.*)$ new_product_images/$1/$2/$3