Hmm. I don't quite know what you're doing: you said you're getting away from --with-pydebug, but these "bad leading pad byte" messages can't be generated unless Python is compiled with (at least) PYMALLOC_DEBUG defined.
That said, my advice remains the same: whittle down the program (instead of fiddling with tools) to get a failing case as small & fast as possible. In your "few dozens of seconds at most", many _millions_ of things happen, and there's scant chance of out-thinking them.
In the newest traceback (core.emerge.8425.gdb.txt), Python detected the corruption while running its cyclic-garbage collector. Forcing gc to run more often may catch the corruption sooner (use Python's gc.set_threshold() to force more frequent collections).