It seems that some dependencies which should be returned by the tooling API are not actually being returned.
This seems to affect only the tooling API and not the Gradle eclipse plugin.

The problem seems to depend on when dependencies where being declared by the build (i.e. dependencies that are declared 'too late' are not included.

This issue was raised by an STS user on the STS issue tracker:
See https://issuetracker.springsource.com/browse/STS-2473
For nice and small sample project that demonstrates a problem case.