As Blerkington said, Auto Find (afaik regardless of the source) actually use your Spot skill rather than (or in addition to) your Search -5 as the abilities say they should. So yeah, gotta raise your Spot to match.
Also, they have a limit on how many "traps" they can find at once. Each component of a trap counts against this limit, so if a single trap contains 10 spikes that shoot up from the ground, then walking near it counts as trying to find 11 traps (the 10 spikes and the one trap box). I don't know what the limit is, but if it's 8 for example, then you'll auto detect 8 of the 10 spikes and no trap box. If you then move away, out of range of the auto-detect, then move back in range, you will then find the rest of the components (up to the limit again vs the rest of the components).
Again, I do not know what the limit is, but I have observed this behavior many times in trap heavy places.