Des Weiteren sollte man eventuell noch Caching einbauen.
InvalidateRect clippt zwar den nicht geänderten Bereich (sorgt also dafür, dass unveränderte Teile nicht neu gezeichnet werden), die OnPaint Routine wird allerdings trotzdem komplett durchlaufen. Das komplette Zeichnen ist aber prinzipiell nur einmalig beim Start des Programms notwendig.
Das ist eine Frage von Aufwand/Nutzen (und persönlichem Geschmack).
Einfacher ist es sicherlich, bei Änderungen ein komplettes neues Bild zu generieren. Bei den vorliegenden Anforderungen geht das sicherlich auch rappelschnell. (In meinem Demo bewegen sich tausende "Controls" auch schnell und absolut flüssig.)
Wenn man die geänderten Bereiche ermittelt und nur die neu zeichnet, muss das bei der geplanten Bildgröße und Komplexität nicht schneller sein.
Ich würde zunächst erst mal den einfachen Weg versuchen.