A very clever person has written a DLL called ApiHooks which will sneak in between a running program and any the Win API functions you choose, and divert the function calls through your own DLL !
I didn't see source code for the ApiHooks, but I can live with that.
Documentation is minimal, but there was enough for me to get it going.
There is a Delphi example of its use. APIHooks lets you hook another program with no instability or apparent slowdown of Windows. You can hook just the API calls you need.
Get ApiHooks from
http://www.anticracking.sk/EliCZ/
ApiHooks lets you write a DLL and attach it to the process you want to hook. You then have to communicate between that attached DLL and your application. I am using a memory mapped file which makes an area of RAM accessible to both the DLL and my application.
Based on my experience, you'd have no trouble hooking gdi32.CreatePalette with ApiHooks.