Now here's a subject close to my heart!
Anjum Anand did some good recipes for the BBC:
This Malaysian curry's the best I've ever made at home, really tastes restaurant quality:
A simple coconut and seafood curry recipe | Life and style | guardian.co.uk
This is dead easy, just needs some adjustments to make it paleo:
Baked chicken curry - Channel4 - 4Food