If you don't want to pay for nothing, see if you can find someone who is prepared to be paid on results, e.g. they will get you to position x for a given keyphrase, and then you have to pay them per month this result remains.
Probably exactly the way to find a snake oil salesman, it is possible but very rare, that a company is big enough that it is prepared to risk revenue in this way. Don't forget that SEO takes many hours of work, from very technical (worth over £75 per hour ) to very labour intensive(i.e. many hours at less money). Only big companies can genuinely risk cost versus revenue, but the big companies don't need to take such risks to win your business as if they are any good they they have reputation and repeat business from existing clients.
So that leaves you with small operators, one man bands and micro firms. If you are a one man band, if you are good enough to guarantee results, then why would they work to make you rich, they would works to make themselves good. There was a young lad on her a year or so back, who was transparent on his income - he was earning £100k p.a. from his own SEO work on his affiliate sites, he also did 'consulting' - which means by the hour.
So that leaves you with the SEO's that are not very good and desperate for business, who will offer guarantees. And they are the snake oil salesmen.
A long while back, when we offered SEO for third parties, someone from UKBF contacted me and actually got a bit angry when I explained that I would never offer guarantees, he basically said 'tough luck' there are lots of firms that do - so he went off (no idea of the outcome), but I did do some research on it.
I spoke to a firm that guarantees (a medium size offshore operation) and the boss told me that they way they can offer guarantees is
1. never let the client pick the key words - if they do, explain to them why those key words wont convert and if you cant persuade them to use 'your' keywords, walk away
2. charge a an initial (non refundable) fee, the set up fee covers the actual work, do the work, if it works then you start getting a 'bonus' which you can then use to fund work into the account
3. have a water tight contract that ensures the clients has no come backs
There are also many blogs out there that explain who unscupulous firms guarantees position 1 including,incredibly, making sure the contract is about ANY type result on Google SERPs, and then they simply put up Adwords with enough budget for one click a month. And then they can provide screen shots of you in position 1 (until you get a click) once a month, tied into a 12 month contract. Whether that is a true trick or not I don't know.