Ask for references...
When you do get the domain name and the keywords it was optimized for and verity the search engine(s) it's optimized and positioned in.
We offer a list of up to 100 clients we can prove we've ranked in the top 10 and anyone is welcome to call them and speak with them.
Any
SEO firm that can't give you at least 5 clients they've helped rank and position well in the last year you probably shouldn't use.
Careful going back beyond that as positioning is an ongoing thing and many clients may only want the one time service (meaning they may have slipped to page two if they didn't opt to continue).
All the best,