Oceans13 is correct.
I work in the North Atlantic Area of New York Center. One of the contracts that we set up with ADS equipped aircraft is a 5 mile Lateral Deviation Event. If you deviate more than 5 miles off of your route of flight, your FMS will rat you out. The ADS report that we get is very accurate and, as Oceans13 mentioned, we can see exactly where you are and where you should be. Upon receipt of a Lateral Deviation Event report, most controllers will simply up link a weather deviation clearance with a time/position to rejoin by. There are a few of my co-workers who will first ask you if you are deviating but what's the point? We already know that you are.
Our response time to CPDLC requests is very low. Usually less then 2 minutes for a climb, even less for a deviation request. Your best bet is to ask before you deviate.
BTW, one of the other contract rates that we set up is a 20 minute periodic report. That means we get a position report every 20 minutes regardless of route. This is nice for the you guys because you can basically fly point to point and not have to fly specific routes. So if you wanted to go direct from 40W to point on the other side of our FIR, it shouldn't be a problem provided that there is no traffic for you at the time of your request.
Hope this helps.