Дайте и мне шашкой помахать! :)

ну, для начала, смотря как движутся объекты...

если, к примеру, по 1-2 точки, то можно кроме самого объекта рисовать рамку в 1-2 точки цветом фона (если он однородный), тогда предыдущее изображение будет затёрто самим объектом.

если нет, то
надо запоминать, то что было на фоне, потом рисовать поверх старого объекта и затем рисовать новый в новом месте.

или

перед тем как рисовать объекты полностью отрисовывать фон.

к тому же:

тут надо использовать Мутех. Для синхронизации.
первым право на мутех должен получить поток отрисовки фона.
потом он его отпускает и дальше кто первый его схватил, тот и рисует.

или, если идёт запоминание куска фона: тут вообще с мутехом классно: всем потокам поставить WaitForSingleObject на Мутех перед процедурой рисования. Пока у одного мутех, он затирает старый рисунок, не боясь, что туда в этот момент кто-то что-то нарисует, потом рисуется на новое место и отпускает Мутех.

Правда, если потоков слишком много, есть вероятность, что некоторые Мутеха не получать :) Тут уже надо раздавать приоритеты...

автора если кто-то нарисует в промежутке между запоминанием куска фона и отрисовки объекта (затирание старого рисунка и созданием нового)
Да, кстати, когда второй начнёт восстанавливать фон, он как раз отрисует кусок первого.

Но это должно работать, если объекты не пересекаются.

авторда забудьте вы про потоки!
кто вам вообще эти потоки в голову вбил?

И то правда? Зачем тут потоки?
Если идут какие-то процессы в потоках, то пусть они своё состояние в какой-нибудь глобальный массив складывают. А оттуда один поток берёт всю информацию и отрисовывает.