I don't think I can do it with just CPANDeps' XML, I would likely have to poll many sources to get that information.

Does the "depth" field tell us anything useful in regard to a module's position in the dependency chain ?

I certainly wouldn't advocate pulling in more sources, as the nice feature of this script is the promptness with which it provides the information.
The only other thing it fails to detect is the case where the version of the dependency that is already installed is not sufficiently recent. (To remedy this would also require significant additional overhead.)
Anyway, like I said, I'll be making good use of it as is ;-)

I opened up one of the XML files in my browser, and found this near the beginning of the file:

This is an experimental XML interface.
It's structure and location may change.
If you want them to change, please ask.
Please try to avoid kicking the shit out of my server,
it's only little and doesn't like being bullied.
[download]

So there's a couple of things of which we need to be mindful.

Cheers,
Rob