OK, so within minutes after posting the question, I found the answer myself here:
https://github.com/npm/npm/issues/2119#issuecomment-5321857
The issue seems to be that npm is not that great with HTTPS over a proxy. Changing the registry URL from HTTPS to HTTP fixed it for me:
npm config set registry http://registry.npmjs.org/
I still have to provide the proxy config (through Authoxy in my case), but everything works fine now.
Seems to be a common issue, but not well documented. I hope this answer here will make it easier for people to find if they run into this issue.