Best thing you can do is to get some sort of portfolio or past examples.

Also be wary of those that make promises that sound too good to be true, SEO takes a lot of time in competitive niches.

Finally educate yourself in SEO, terminology and methods, as well and simply try to have a live (phone or skype) conversation and see if they are knowledgeable or not. You can usually get a feel of whether or not someone is very "with it" by simply talking for 10 minutes.

I would be asking them to show previous ranking successes and also talk in DETAIL about how they did. I'm familiar with most SEO techniques and practices, so my concern would be trying to root out someone who talks up a good game but doesn't know the fundamentals to actually achieve the results they are touting.

Remember its all about the details. I would also ask them ethical SEO questions, so I could get a feel for exactly what they would be doing for my sites.

How about asking about the latest major changes in the world of SEO, including algo update and consequences?

in seo 100 % guarantee does not exist. Only noob seo give this type of guaranty.

you check site seointerviewquestions.in there i found some tricky questions may be it also helpful to you

Ask about Google latest updation. Facebook and twitter impact on ranking.
Difference between {follow, no index} {no follow, no index} {follow, index}{No follow, Index }
How forums submission will be helpful in getting SERP?
How can we generate traffic from Social Media Sites ?

I agree with this!

In addition to this ask for the URL of a site they worked on and check to see how it ranks and performs.