Suppose my car breaks down and I take it to the car mechanic guy and he looks it over and says it will cost $1000 it fix it, and I say ok thanks. I come back later and pay the $1000 as agreed and he says 'thanks. By the way I tried my best but it is not fixed. For another $1000 I could try some more or I guess you could try another mechanic'.
I wouldn't be happy with this and would be saying 'give me my ******* $1000 back'. The fact that the guy tried his best is no good to me - I am interested in is the car fixed or is it not fixed. If I wanted someone to not-fix my car I could have just given the $1000 to my granny who knows nothing about cars.
So I think an honourable mechanic would not say the above but would either keep going until it is fixed without asking for more money or offer a refund. The point is that the if the original quote of $1000 was too low this is the mechanic's fault and also that it is unfair to the customer to say 'OK I can fix your car for $1000' and then after some period of working on it say 'oh yeah sorry you know when I said $1000, I actually meant $2000'.
If the job turns out to take longer than expected it might be because there is some genuine difficulty but alternatively it might be because the mechanic is lazy and / or not up to the job.
So I think some customers think about SEO in this way and I have some sympathy for this thinking - the customer is interested in results (such as getting on page #1) and wants to pay for results not for excuses. I know that an SEO guy cannot force a page # 1 result but he can agree to share the financial burden of failure.
Or in another example, commercial contracts (such as building a house or whatever) often or always have various penalty clauses built in to deal with various degrees of failure.
So is the customer wrong to think like this or is it common / normal to have some kind of refund / guarantee policy built into an SEO contract?