Checking a publicly-available URL blacklist is a good idea, thanks!
I may well end up adding a captcha of some sort. However, that effectively means I can't have a public "create a DecentURL" API call like I do now -- they'd have to sign up and have an API key or something. That's a bit of a bummer.
The utility of an API for this sort of service is honestly pretty limited. If you're doing things right, most of your links should be getting created by casual users (for pasting into chat/email/twitter) - it's not too much of a hassle for them to hit your site and fill out a form.
Rate-limit link creation based on the user's IP.
Check submitted links against a URIBL. Prevent users from adding links which are on the blacklist, and remove links which appear on the blacklist.
Reject links to newly registered domains outright.