Find relevant domain/hosted zone under which to host subdomain
Short answer: I don't believe that is possible.
In my opinion, I suspect this problem has more to do with process and responsibilities than it does with Terraform.
You said:

It's possibly that I could go with the fist approach (e.g. where example.com is my only hosted zone) only for someone to later add a hosted zone for the mysite subdomain. If that occurred I wouldn't want to have to change my code...

Terraform is best when at least most of its associated resources are Terraform-managed. That means you should be managing your zones, too, not just your records.
Which begs the question: why isn't your zone in Terraform?
If your zone was Terraform-managed, the impact of that change should be evident in a terraform plan to anyone who might come along to change it. Even if it references a zone in a different remote state file, a tool like runatlantis.io could show that diff in the Github PR before merging.
Let's say this is the worst-case scenario: you managed the records, it's a different team that creates and manages the zones, and they don't want to use Terraform. In that case, perhaps your DNS records shouldn't be in Terraform, either. Terraform is arguably too stateful for that. Perhaps a few python boto3 scripts can do everything you need it to.