It really does sound like inadequate cooling. Power will drop if the tec's can't keep up due to not being able to move the heat away. And especially with the red's and blue's getting hot too, it really does sound like a cooling issue.
Things to verify would be to make sure both surfaces are smooth as any gaps / warping / dirt could really limit the heat transfer. Also, did you use a good quality thermal compound between the laser and heatsink ? If not, that's something that can help immensely.
Make sure it's a nice heavy baseplate or heatsink, the more aluminum the better. Make sure it is in fact aluminum or copper.. Fans can help but not a substitute for good old mass.
If you can, post a picture of the setup. Can really help in diagnosing the issue.