Rebuild and deploy everything, what's the actual problem? Like the OP said, that's a scale issue and most projects don't have it.
Also building/testing is far more effective at finding dependencies than just going by repo structure. There are numerous package managers available to solve versioning if you need separate components.