What are the temps like with the stock coolers? My old 4870 crossfire setup ran cooler with the stock coolers than it did with both cards under an accelero twin turbo. This wasn't due to the cooler - the twin turbo is amazing with a single card, but rather the spacing.
The aftermarket cooler was thicker than the stock job, meaning there was less room for cool air between the cards. It also had less directional airflow than the stock ones, the stock jobs suck in air and dump it out the case, the aftermarket ones hardly exhausted anything - raising ambient temps local to the cards.
Another less likely possibility is that your install of the coolers my have been less than superb - doutful though judging by the sounds of how many times you;ve swapped them over.