The FE guy seems to think that upgrading Npm wouldn't fix it, because "Some kind of caching mechanism kicks in, and the only way to really resolve it is by nuking everything and starting from scratch. This is because we use git tags (github release tags)."
Does that make sense?
Suggest they give this a try as a first port of call. After that it's worth figuring out if the dependency tree is purely massive and you're fetching thousands of packages per install, or if its the NPM service responding slowly, in which case a local proxy in your business may well help here; I'd recommend https://www.verdaccio.org/