Problem using Relays at 220V with 595
You need to learn how to read data sheets. Start with the 595 http://www.nxp.com/documents/data_sheet/74HC_HCT595.pdf So you're looking at the maximum current limits (25 mA) and that's more than your relays require (15-20 mA), right?

Nope. Look at V(OH) lower part of page 8. This applies to the 74HCT595, but that's OK because it's running at 5 volts, and the output drivers are the same between HC and HCT - it's only the input structure that changes.

For an output current of 6 mA, the worst-case output voltage is 3.7 volts, and it just gets worse as the output current increases. To put it simply, the 595 simply doesn't have a strong enough set of output pins to reliably drive the relay cards. I'd guess that the only times you actually get some relays activated is when only 1 or 2 channels are driven on.

In order to get reliable operation, you'll need to buffer the 595 output with something a bit stronger.

EDIT OK, using pull-down discredits my answer. Sorry for doubting you. Your 595s ought to be working. Just like you said.