Yeah... about that... you can't "buy" placement in the organic listings. The only thing you can buy your way into with Yahoo is inclusion in their paid directory, inclusion in which is not necessarily a bad thing - it is a strong link for Google, and it might have some small impact on your rankings in Yahoo's search. However, in most cases that is something you would pay Yahoo for directly.
The only other place you can pay to be listed is in the Sponsored Results. This is the only place I can think of that the
SEO company would be putting you because they mentioned you would pay by the click, and there is nowhere else on Yahoo that you would pay to be on a per-click basis.