Talked to Antonio privately and it appears that gcrypt run in fips mode for some *unknown* reasons. This has the side effect to run some self tests on each program linked to libgcrypt (I think) and those self tests exhaust /dev/urandom somehow. The gcrypt fips mode is activated by the presence of /etc/gcrypt/fips_enabled file. And removing this file solves this issue as well as bug #1096050. So I guess the question is now how was this file created at all.