Lintian is currently run over the entire debian archive on master. I can not assume a package or its depends are installed. I had considered the equiv of shlibs files, but it only works in the case you describe.