What is the most appropriate way to notify/request permission from an ISP related to white-hat security testing?

I have never asked for permission in advance (that I can recall), but I can say clients on many occasions have reported IP addresses under my control to be attacking them.

For example:

TOS Violation - Malicious Activity

We have received a report of malicious activity originating from an IP address assigned to (redacted). Please investigate this complaint and update this ticket within 24 hours to avoid a disruption in service.

Most often my clients simply neglected to check the list of authorized IP addresses I mentioned I may use during testing.

On every occasion, after answering a TOS violation, the ISP goes to verify with the target that the activity is authorized and all is good.

Note: Amazon now makes it easy to ask for permission in advance: http://aws.amazon.com/security/penetration-testing/ (I have heard others do as well now)

I used to always build in a contractual requirement that the client had to get ISP signoff before we would agree to any remote testing. Effectively this was a 'hold harmless' letter explaining that the tester (us) would be using techniques that could look exactly like a real attack. The key is that the client requests it, using our template

We did this with ISPs in the UK, US, Europe and Asia, but just to clarify, most these clients were generally multinational corporations with dedicated ISP relationship managers in each territory etc. For smaller, local clients in Scotland we did the same, but the ISPs were often local too, so your mileage may vary if you have a small client and a large ISP: the ISP may not care.