That didn't sound right, so I took a quick look at the level four trainers on the market right now, just as a quick snapshot. Of the next ten level 4 trainers listed, only two have a salary under $20,000 and 8 are above that line. The bidding on the two under that line is at $520,200 for Leo Belu and $173,400 for Achacjusz Anonim, an auction with more than seven hours to run. Of the other eight level 4 trainers, only one has a salary in the $20's, and his bidding is already up to $325,000. Three salaries are in the $30's, three in the $40's, and the final guy has a salary of $79,340 (he also has a specialty).
So, upon closer scrutiny, a nice "calculation" turns out just to be a story. I would like to see fair calculations on this topic.
$20k is actually a high estimate. I generally would pick up a trainer with about 13-14k salary for a very low signing bonus and keep him until roughly 18k or so.
As far as the discrepancy you're observing, I think it's almost certainly the case that you picked the fourth level listed in the search dropdown and saw the trainers with "superior" skill. Because you can't search for staff with minimal skill level (level 1), the dropdown starts at basic (level 2). Level 4 is advanced, and it should not be too difficult to find guys at ~14k within a few days that you have to pay less than 5k to sign, though of course if you're patient or willing to spend more, you can get them at 11k salaries or even slightly lower.