Let's Encrypt goes by the "Authoritative Nameservers" for any Domain/Subdomain. So it's actually checking domain.com's NS's for the key.
The workaround, is to redirect the NS Authoritative domains. In your example, in domain.com's NameServers, add the following
staging 600 in NS (Your Servers Nameserver1 here)
staging 600 in NS (Your Servers Nameserver2 here)
now when LE looks up staging.domain.com, domain.com's NS say: whoops staging's NS is ..., look there.
This will also include ALL subdomains for staging.domain.com, so client.staging client2.staging etc will all use your servers Nameservers