I think I figured out the issue. None of this is tested with TAS, but I am pretty confident in my frame data knowledge.
If I wanna do an early uair with Falcon, I press X and up+A. Notice that my uair comes out as soon as possible, meaning I press A on the 5th frame after I pressed X, since this is the first frame that Falcon is airborne. Somehow - even with tap jump turned off - the up input on the control stick sometimes gets mixed with the X input, making the game think that I held jump for more than 5 frames resulting in a full hop. If tap jump would have been on, the result would have been a double hop.
Now I use the same method in Melee, and I almost never screw it up. I uair this method out of shield, during combos, after pivots etc.
Also keep in mind that in Melee, you cannot hold X for more than 4 frames for a succesful double hop with Falcon, where PM gives you 5 frames to work with. (He is still airborne on the 5th frame in both games.)
I shouldn't even have to turn off tap jump, but for some reason X/Y+control stick up gives weird results in PM...
Also, this was all tested in 3.0, it might not be an issue in later versions, but I will test it when I get my hands on it.