Welcome to wmw Nick!
Yes it can be a slow process, but it is unnecessary to submit to Google or any other engine monthly. I have sites that have been submitted only once, or none at all (used a link on another page and let the spiders find it). They remain in the various indexes out there, and gradually they get picked up by others too.
There is nothing (ok very little) you can do to influence how quickly or how often your site gets indexed, except for pulling out a credit card at the Pay For Inclusion, or PPC engines. Mostly some patience is required, but you can make the changes you deem necessary all at once, it's just that you'll end up gradually tweaking that page anyway, unless it ranks well right from the start, and it will take time to see the results of those changes.
IMO A sloppy cloaked page is one that is easily discerned by surfers and search engines to be unacceptable (in the eye of the beholder), but maybe a more general definition is any page that hurts your site and rankings instead of helping can be considered sloppy.