I have two 5870s, one XFX and one Sapphire. Both manufacturers did a terrible job applying the thermal paste. Reapplying it dropped temps by 10c on the XFX and 11-12 on the Sapphire. I didn't note the temps on my 5830s or my 5770, but there were improvements in every case.

A couple of tips:

1.) Often the heatsinks sit slightly off kilter, so you might need to use more paste than you would for a CPU.

2.) Again because of how the heatsinks sit, you might get air bubbles if you try applying a thin, even coat. I've had more success putting a large drop in the middle of the GPU and letting the pressure of the heatsink spread it out.

3.) If you use Arctic silver or any other conductive/capacitative paste, be careful not to get it on the electrical components as some people have killed their cards that way.