Python equivalent of find2perl
If you're trying to reimplement all of find, then yes, your code is going to get hairy. find is pretty hairy all by itself.
In most cases, though, you're not trying to replicate the complete behavior of find; you're performing a much simpler task (e.g., "find all files that end in .txt"). If you really need all of find, just run find and read the output. As you say, it's the gold standard; you might as well just use it.
I often write code that reads paths on stdin just so I can do this:
find ...a bunch of filters... | my_python_code.py
There are a couple of observations and several pieces of code to help you on your way.
First, Python can execute code in this form just like Perl:
cat code.py | python | the rest of the pipe story...find2perl is a clever code template that emits a Perl function based on a template of find. Therefor, replicate this template and you will not have the "hundreds of permutations" that you are perceiving.
Second, the results from find2perl are not perfect just as there are potentially differences between versions of find, such as GNU or BSD.
Third, by default, os.walk is bottom up; find is top down. This makes for different results if your underlying directory tree is changing while you recurse it.
There are two projects in Python that may help you: twander and dupfinder. Each strives to be os independent and each recurses the file system like find.
If you template a general find like function in Python, set os.walk to recurse top down, use glob to replicate shell expansion, and use some of the code that you find in those two projects, you can replicate find2perl without too much difficulty.
Sorry I could not point to something ready to go for your needs...