I had similar problems and fixed them with the way I created DC's and set the rendering. Look at the update area in the paint, see what is being redrawn.
I don't like to use SaveDC() / RestoreDC().
I keep the objects released from the SelectObject and replace these and delete the created ones before the function exits.
I do not do any drawing in the paint function except to BitBlt() the frame buffer (HDC I send into the paint) to the paint DC. All drawing is done prior to ME calling paint or if windows calls the paint no new drawing is done, the old buffer is redrawn.
I create the DC's ect compat with the screen, set all to half tone rendering. I have no problems with any drawing.
Remember not all paint msg's are called by your program. Controls will call to be redrawn if they are used.