Frankly, if you "don't know where to start", get someone that does. It sounds like the cost of failure is very high, so this isn't the time to experiment and learn from mistakes. Find someone that knows this stuff. You can look over their shoulder and try to do as much of the grunt work as possible so next time you're the expert. I think I underestand the basic principles pretty well and could get something working. However, for extra high reliability there is usually much lore and experience that you wouldn't guess from the physics alone. I wouldn't take this on myself without a expert to at least ask occasional questions of and to bless the ultimate design. So from a non-expert view, here are some thoughts:
First 45C isn't all that hot. It's only 113F, which is not out of line for summer shade air temperature in various parts of the world. Ordinary electronics gadgets, unless specifically for lab use or other environmental constraints, will have been designed to run at 45C ambient. Think about it. If you left your cell phone on the dashboard of your car parked in the summer sun in Phoenix, you probably wouldn't blame it for not working. Of course you probably couldn't hold it without hurting yourself either then. But, if you were standing outside under the shade of a tree mid afternoon in summer in Phoenix, you'd probably be pissed of if your cell phone didn't work. That's 113F.
Second, two other advantages you have is that this 45C is highly reliable, and essentially infinite. In other words, it's 45C all the time whether its summer or winter on the surface. Also, you can dump a few kW into a reasonable size "room" of this mine, and it will still be 45C.
So the best solution, as Russell also pointed out, is to spec things so that they run fine at 45C ambient. Space them out enough so each thing sees the 45C ambient, perferably without needing any forced air cooling. That way you don't have to worry about what happens when the coiling breaks down. Again, most off the shelf electronic gear should already be fine with that. Lifetime may go down, so derate. Get good quality stuff that should last 10s of years normally.
If you really need cooling, my first knee jerk reaction is to build a small room and put 2 or 3 air conditioners in it. Make sure any one air conditioner has the capacity to cool the room sufficiently. The multiple air conditioners are for redundancy. You seem to say it's only a few kW, which is small as airconditioners go. 1 kW is only 3400 BTU/hour. Also, it sounds like every last item doesn't need to be cooled, so some of the power you need can be dissipated outside the room and doesn't add to the air conditioner load. 113F isn't that hot and there are certainly off the shelf air conditioners intended to work under those conditions. Having 2 or 3 units always on cooling the room is for reliability. However, this is a area you really should consult an expert on.
With the much reduced use of DIP ICs, few component retailers offer DIP heat sinks any more (and possibly few of the younger electronic circuit designers know about the stuff!). However, if you are looking at personal / DIY use, glue-on DIP heat sinks in anodized aluminium are available, often as "new old stock", on sites like eBay, and surplus vendors.
For instance, I found this on eBay for under $1:
While it is designed for 14 to 16 pin DIPs, it is trivial to chop it down the middle and use half for an 8-pin DIP.
Thermal paste between the heat-sink and the IC would be useful, or one could use peel-and-stick thermal paste pads for convenience:
Some form of clamp would also be needed to hold down the heat sink, if glue-on isn't good enough.
Alternatively, 2-part and slide-on heat sinks for DIP used to be quite common, and can still be found as "new old stock". These eliminate the need for a clamp:
However, these heat sinks are not as convenient to use for a smaller DIP, such as an 8-pin package.
Finally, sometimes one would sand the face of a metal coin flat, then clamp it onto a DIP IC, as an interesting-looking heat sink. End of history lesson :-)
Best Answer
When you see a heatsink with a screw, that is because the chip it is mounted to has a hole for a screw mount.
Sometimes the plate that you have to heatsink is going to be a different voltage then the surrounding board, so you need to use something that is electrically isolating, but thermally conductive. These replace the need for conductive paste.
If you have the area of the regulator/IC that generates heat at a voltage like ground, and the other connections for your heat-sink will be ground, you can connect them directly, and you normally want to use a form of thermal paste. I have attached a heatsink without thermal paste and still had a device temperate at almost 90 degrees C. After adding thermal paste it measured at 5 degrees C above room temperature. Often being able to connect your heatsink to ground via solder helps dissipation as it dissipates to the ground plane.
In computers you have a very specific task, cooling the Processor. In electronics it can be a very large range of tasks, and often you are willing to pay more to cool something because you design calls for it, or you are willing to pay less because your design does not need some very nice thermal paste.
In general, you are going to just want to use thermal paste, you do not have to worry about insulating your heat-sink if you leave it floating in the air, or ensure where it mounts to the board there is not a voltage connection. This keeps things simpler for a tinkerer. For any chip you get that you think needs heat-sinking, read what they suggest to do (on the datasheet), and follow it.
Last but not least, thermal paste for computer processors will work for ICs.