Varnish poisoned cache avoidance

[pub crawler]

We have some ban / block logic in our application server behind
Varnish.  For instance, when we have a comment spammer or other
repetitive troublemaker messing with our applications we ban their IP
in our application server.

A person or bot returning after being blocked will still reach our app
server, but it just returns a page that says BANNED.

We had such a banned IP request a page and subsequently I requested
the same page and was given the BANNED message as it was sitting in
Varnish cache - even though my IP is not banned.

My question here is how best to prevent this and what sort of
workaround other folks have for this?

I've considered banning at our firewall level, but it's too time
consuming to do so and the block lists are so long that it really
causes the firewall to take forever to restart from cold reboot.
Originally I had blocked at the firewall, so I've been down that road.

Any input would be greatly appreciated...

-Paul