"The a/b/c etc subfolder system sounds like a good option, to keep a max of 9999 ID folders in each subfolder, if I have understood it right."

Yes, and it is a proven option, as mentioned in a related forum thread.

We do this now on several sites... one of them with ~1,000,000 users and ~8,500,000 images... and it works great.

-Smoge