The easy answers are 1.) move to ext4 and/or 2.) "shard" the directory somehow - by placing them in sub folders either numbered or lettered.
These changes won't be easy to make though so I'm looking for some creative solutions. Any ideas?
Really you should not choose a "creative" solution if you have a simple, effective, and more correct way to do it. Just because the migration isn't easy to implement, the creative solution, in my experience, usually ends with a much bigger headache down the road and ending up having to do it the "right" way anyway.
It sounds like you already know better answers of what you should be doing instead...
You've identified the best approaches/fixes to the problem. There's no shortcut available to you at this point. The ext2/ext3 filesystems have a hard limit of 31998 links.
Of course, the XFS filesystem is another nice solution for this... Can you provide more information on the application and reason for so many subdirectories?