More info is needed on how your guestbook is set up. Do users need accounts, or is it just a free-for-all?
If they need accounts to post, then simply disable the accounts of the offenders.
If it's a free-for-all, then there's little you can do to stop them.
One idea is to require a random security code before a message is posted. I'm sure you've seen those on the web. Most spammers would flee once you do that.
I run two web sites hosted by 20m.com, and each has a guest book. In both guest books, I've been getting 40 or more fake postings a day with ads for everything from online drug sales to really nasty porn. I go in every day and erase them, but I'm thinking there has to be a way to stop them before they post. My host help desk said I could password-protect the guest book, but that kind of defeats the purpose of having a place for folks to post their thoughts freely on the actors for whom the sites were built. I'm considering taking the guest books offline for a whil to see if the ad jerks go elsewhere and for get about me. Any other suggestions? The sites are:
http://bobeinstein.com
http://jeffreywright.20m.com
I don't know if this is the right place to post this, but it seemed the best shot. Thanks.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic