If they're tampering with the actual traffic on port 53, as opposed to just records from their own DNS servers (the impression I got), then you could probably prove it by using DNSSEC (will only work for certain TLDs though, .org is probably easiest).
Ehtyar.