I admit, I no very little about contracts when it comes to SEO jobs. I do not sell "SEO Services", I do not offer "guaranteed positions" and I don't pitch that I will rank your pages in the top results. So when it comes to contracts for me, I do not have to worry about things outside of my control (i.e. Google's Updates, Sandbox and others). But that does not mean that I do not put everything I know into ensuring a Web site is properly coded for the engines and have an outstanding internal linking structure. But I sell Web applications and high end Web sites, not top rankings.
For those of you that sell SEO services and you are looking to protect yourself, from what you need protection, check out a thread at Search Engine Watch where moderator (and I believe former lawyer), mcanerin, posts a detailed sample SEO contract.
Be warned that it was intended to be a very complete version - I have another, simplified version I use most of the time. This one is so complete it's been known to scare away small business people who are used to dealing on a "handshake" level.
On the other hand, if you are dealing with a large corporation or a client that is in a foreign territory, this can be very useful for spelling everything out.
Plus he is willing to explain the details of the contract if you have questions.
At this point, the contract is not downloading, seems to be down at the moment. I'll check back later.