Yeah but I don't think it's that legislation you'd rely on: you paid for a service they didn't deliver.

Compensation yeah, only applies if the reason for the delay/cancellation was under the airline's control. Nats down is pretty clearly a reason to reject compensation claims.