Welcome to WebmasterWorld!
I'm not going to touch on the issue of specific companies, but I will give you some basic questions that might help you determine your clients overall cloaking comfort level. That in turn should help you figure out the type of company/consultant and/or product that might be the right fit.
1. What Kind of Search Engine Traffic Do The Currently Receive?
The level of risk a company should be willing to accept regarding the possibility of getting banned or blacklisted should be based on the potential loss they would suffer if that were to happen. If they are completely dynamic and have never received any kind of search engine traffic, then the upside (a bunch of new traffic)is high and the downside (getting kicked out of a database they've never been in to begin with) is low.
If they do get a decent amount of search engine traffic and they are considering cloaking to deal with a particular section of their site, or they simply want to improve their current positions, then the potential downside could be quite high.
2.What Type of Cloaking Are They Interested In?
Cloaked content can usually be broken down into two categories:
A) Promotional or Doorway Cloaking or
B) Content Cloaking
Promotional cloaking would be developing traditional doorway type pages that focus on terms that relate to the content of the site, but are not a deriviative of any particular page of the site. Quite often these types of cloaked pages deliver users to one specific location.
Content cloaking involes delivering pages to search engines that are built from content that exists on the site. An example would be if you were to generate SEO friendly pages from a product database. In a content cloaking scenario, each cloaked page tends to have a specfic landing page attached to it.
Of the two basic types, search engines tend to be far more tolerant of content based cloaking. Engaging in promotional cloaking greatly increases your chances of having a competitor complain to a particular search engine.
3. How Search Engine Friendly Is The Site?
Forget about the dynamic issue for a minute. If the pages the site serves were static, would they stand a chance of ranking well? If the overall design/structure is sound and the ony issue you're dealing with is query strings, then cloaking might not be the best answer. There are several new companies out that offer a wide range of tools that deal with dynamic issues. Some are database conversion tools that allow you to simply republish your database in a static format, while others are programming modifcations that remove the dynamic appearance of the site. They come in all different shapes and sizes, but most do a good job with dealing with the dynamic issue.
On the otherhand, if the site also suffers from a long list of design related problems, and correcting them isn't something the client is willing to do, then cloaking might be the best alternative.
How Competitive Is The Overall Set Of Keywords?
If the keyword set your client wants to go after is primarily a small list of high-profile terms, cloaking will not be very effective because of the effects of directory listings. If you don't have a decent chunk of terms that do not pruduce directory matches at sites like MSN and AOL, cloaking might not be worth the expense.
5. Does The client Have A Paid Inclusion Budget?
In today's search engine marketplace, the engines that are the most tolerant of cloaked content are not the engines that still operate a quality free-crawler. Unless your client is willing to live or die by Google alone, they will need to be prepared to pay to submit the content to Ink/AV. That can sometimes add up to a decent chunk of change that isn't usually included in the budget that gets setup to develop a cloaked solution.
If you get a good handle on the answers to these kinds of questions, the differences between the various cloaking business models will probably be a bit more clear, which should help you make a good decision either way.