Для плавности важно не только что время есть в запасе, но и вывод кадра в строго запланированное время. Что бы было видно, достаточно что бы задержка при показе кадров плавала от 0мс до 40мс. Потом, видео-каналов момент быть много и все они будут друг на друга влиять. По коду, к сожаление, не видно как вы инициируете WM_PAINT. То что вывод связан с WM_PAINT, уже, говорит о том что вывод всегда будет с непредсказуемыми задержками и рывками, если только не создать отдельный цикл выборки сообщений в отдельном потоке, который рендерит. Но зачем это делать, если есть DirectX. Весь смысл такого сложного дизайна — показывать кадры со строго заданной частотой (насколько это возможно в системах не реального времени), а также нивелировать случайные непредсказуемые задержки и нагрузки CPU. У нас, типичная задержка при непосредственном выводе кадра — микросекунды (0 мс). Также, для плавной синхронизации, я очень рекомендую завести аналог референс-часов, по которым все компоненты синхронизируются друг с другом (в случае стереоскопичекого видео или звука очень даже актуально). В противном случае, у вас всегда будут проявляться все особенности реализации современных операционных систем в виде рывков…

Наработок куча, так как уже лет 10 пишем профессиональный софт для телевидения. Это масса, достаточно сложных, «технологий» типа ffmpeg, DirectShow, Direct-X. Также весь этот зоопарк используется для кодирования и декодирования видео. У нас написаны свои рендереры видео и аудио максимально использующие поддержку со стороны аппаратуры. Тут, к сожалению, статьей не отделаться, тут нужно несколько книг писать, как все это использовать, применительно к видео обработке. Но собирать качественный рендерер видео из готовых компонентов уже не сложно.
По поводу вопроса про поток который показывает: его задача максимально быстро, без задержек, показать следующий кадр. Задержки больше чем 10 мс на кадр, а особенно если они плавающие, уже заметны на глаз. Подготовка самих кадров и все тяжелые операции должны выполняться в другом потоке. При использовании SendMessage, задержки на переключение контекста потоком не предсказуемы.
По артефакты: я имею ввиду «плавающую» частоту воспроизведения кадров. Когда робот движется, это более заметно.
Задача у вас интересная. Пока, как я понял по коду, решена в черновом варианте, но, при желании, тут много что можно улучшить.

А можно еще несколько вопросов:
1. Почему не используется аппаратное ускорение (например DXVA под Windows) — это позволило бы показывать видео намного плавнее, т.к. загрузка CPU обычно падает до 1-5%.
2. Почему не используется отдельный поток для прямого рендеринга из него средствами Dirext-X. Посылка сообщений из другого потока, таких как WM_PAINT, по средством SendMessage, все-равно происходит синхронно. Т.е. тормозится вызывающий поток, потом стартует тот, которому отправлено сообщение, сообщение выполняется в другом потоке (у вас это WM_PAINT в основном потоке), после управление опять передается в вызывающий поток. Какой смысл отдельного потока, если отрисовка все-равно происходит синхронно в главном потоке.

Это, как минимум, две причины которые приводят к рывкам. Даже на том видео, которое вы прислали, заметно, что частота вывода плавает. Я уверен, что на более динамичном потоке эффект будет еще более заметным.

ffmpeg прекрасно умеет использовать различные API для аппаратного декодирования видео. В частности, для Windows поддерживается DXVA. Современный офисный компьютер (при поддержке со стороны Intel или NVidia) спокойно тянет 25 окон 720x576 (SD). Знаю, так как сам разрабатываю софт для телевидения и мы используем данную поддержку для Multiview телевизионных каналов. При этом загрузка CPU 20%.

Для этой задачи есть уже давно было придумано более изящное, на мой взгляд решение. Стандартная реализация очереди с приоритетом (ваш случай когда весами элементов являются сами элементы) отлично реализуется на структуре heap, где элементы хранятся в сплошном массиве и каждый новый элемент становится в свою позицию простыми обменами не более чем за O(log N). Собственно всем известный heapsort как раз так и реализован. Для слияния нужно просто одну очередь по-поэлементно влить в другую.