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.
Our Commercial Exchange [webmasterworld.com] is the forum that's been provided as a service for members to offer or seek services. You can check the forum charter for specifics if you're interested.
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.