stucco - 11:11 pm on Mar 14, 2013 (gmt 0)
Sounds like a botnet to me.
1. Contacting the 'abuse' address for the ISP is one route to take (may or may not get a response). May result in a few hosts getting fixed.
2. You could block their traffic. They would probably just find another service to do the same thing.
2b. They do use other services to do the same thing; you're just seeing some of the traffic.
3. You could return wrong addresses (127.0.0.1, 192.168.1.1, some internal DISA or MILNET reserved address, or cia.gov) -- that might cause some puzzlement for a bit, but same as #2.
Likely these IP responses (from your server) then get posted somewhere else (IRC, p2p network, some other compromised vps servers etc). No single ISP is going to care about it enough to do much than take care of their hosts.
There may be some interest by Interpol or a military/intelligence anti-cyberterrorism organization (or they might be causing it). I would cantact an organization like this... I remember some big botnet just got shut down in the past couple months, you could try whoever was involved with that.