I'm no lawyer, but i'd do the following:
* Have an AUP that has something akin to the following paragraph:
If you spam, either through us or through another ISP, then your
account with us will be terminated with extreme prejudice. You will
also be charged <some exorbitant sum of money> for our work in
tracking your spam down and repairing our reputation.
Then, you can talk to the other ISP, explain the situation, request that
they forward 10 or so of the complaints to you, and boot the idiot.
Granted, I don't know how this would work as far as contract law goes,
but it seems to make some amount of sense.
-dalvenjah
Hank Nussbacher put this into my mailbox: