Anyone know how to block new posts per category if a limit has been reached?

Hi all,

I'm faced with a interesting puzzle related to my little homemade ad system described here:
The system is fully functional on my site here if you want to take a look:

The ads are custom post types and each ad size posts to specific cpt categories.
There are a limited number of ad "slots" available per size (ie per category).
Each posted ad is automatically deleted after 30 days, thus freeing up another slot.

Here's my puzzle: I'm trying to figure a way to limit the total number of posts that can be in any given category at any given time. Such that, once the limit has been reached, no new posts will be saved and, preferably, a "Sorry, not at this time" type of message can be displayed on the ad submission page.

I've Googled and Googled and scoured the WP codex for clues, but can't get a handle on this. Anyone have any cool ideas?