How to check for the existence of deep subdomains even if the intermediate ones don't exist?

Solution 1:

Suppose that test.example.com don't exists and gives NXDOMAIN when runnning dig on it , but i know that subdomain.test.example.com exists

This is not possible, per DNS specifications. Or said differently: it means the authoritative nameserver for this zone is broken.

See RFC 8020: NXDOMAIN: There Really Is Nothing Underneath

When an iterative caching DNS resolver receives an NXDOMAIN response, it SHOULD store it in its cache and then all names and resource record sets (RRsets) at or below that node SHOULD be considered unreachable. Subsequent queries for such names SHOULD elicit an NXDOMAIN response.

Solution 2:

I agree with Patrick, but would like to provide some more clarity about what the actual expectations are:

If you have records at subdomain.test.example.com but none at test.example.com, that does not mean that test.example.com "does not exist", the term for this empty type of node is empty non-terminal (sometimes ENT).

When you query some name that is an empty non-terminal, the proper type of response is not NXDOMAIN (which would mean "there is no such name") but rather NODATA (which means "there are no records for the requested type", in the ENT case regardless which type you ask for).

For clarity, the NODATA response type is: response code NOERROR, SOA in the AUTHORITY section.

The indication that there could exist further sub-domains is that the response you got was not NXDOMAIN. If you also determine that there are no records at this name (ie, it is an empty non-terminal), there must be some subdomain (one or more levels down) where there actually is something.

The other aspect, which the question implies and Patrick covered is that some nameserver implementations are buggy and send NXDOMAIN even in situations where this is not the appropriate response.
That type of implementation flaw results in serving inconsistent data where what should all be a tree structure is actually broken into pieces that do not connect. That behavior particularly fails in the view of any resolver that relies on previously observed NXDOMAIN responses actually meaning something, as well as not being possible to represent in DNSSEC.