Have you read this?
http://www.thebox.myzen.co.uk/Tutorial/Power.html
What is important is the junction temperature, that is the temperature of the silicon inside the regulator chip. While you want it as cool as possible for reliability as long as this is below the maximum allowable then it is fine. For every ten degrees hotter something gets it's life halfs, approximately. Running a lower voltage into it will reduce the amount of power you have to burn off, depending on the regulator it only needs to be about 1.5V above the regulator's output.
Heat sinks will help but only to a certain extent.