Lance, from some of my experience on other boards (and running one myself for a short while), you'll always get some spam registrations - they're devious little bastards, and they've refined their "skills" to be very effective on infiltrating forums within hours of a forum software update. That said, there ARE ways to short-circuit their process. CAPTCHA is a good way, but the way I found best was CAPTCHA followed by an automatic email to which they MUST reply before they can post; this doesn't eliminate the registration, but it DOES keep the bot from spamming the board. Three or four minutes before reviewing posts was all it took me to check the member lists and delete the spam accounts which never got further than the registration process, and it kept my board clean.
Good luck - this Age of Information we're in is fraught with unethical opportunists who are good at what they do; best we can hope for sometimes is just to maintain parity.