IMO the most relevant solution to your problem would be something called a tarpit.

In a nutshell:

Its software designed to keep port scanners 'tied up'. It accomplishes this by tricking the computer initiating the scan into thinking the TCP connection is open, when in reality, its only half open, and thus has to time out.

The name of hte software I'm refering to is <a href="http://www.hackbusters.net/">LaBrea</a>.

Once you get the theory down behind it, there are more than a few ways to implement it.

Hope this helps!