Forum Moderators: open
Not many offer cloaking as a service on it's own, mostly it is coupled with SEO. There are a couple I've seen that offer cloaking services, from their servers, but I can't speak to their value.
More offer cloaking software, but you have to run it yourself. Are supplemental static pages out of the question? Cloaking is an option, but you also have other choices. Do a quick search on this site for "dynamic pages" and you should come up with something that will work for you.
Brandon, you might also want to read through this forum thoroughly to get the gist of what's involved with cloaking, in addition to doing the search Air recommended for dynamic sites to see what other alternatives are available to you. A search for mod_rewrite could also be helpful, but imo the simplest initial step would probably be to add a number of static HTML pages to the site, as he suggested.