makes me wonder, is there even anything else that they can do to block tethering apart from UA sniffing? given that the phone is unlocked and doesn't have any carrier's crapware in it.
Definitely. Since it's part of the contract that tethering isn't allowed, and (I assume, don't remember) that they can 'terminate service' for anyone at any time for any reason, they could: watch the pattern of traffic to identify well-known desktop apps, completely disconnect the worst 0.1% of offenders on the (very likely) assumption that they're guilty, and demand they pay up. Even a VPN won't hide you there, unless you have something that defeats traffic analysis (a definite possibility, but not a normal tool either, afaik).