Компонент TImage создается динамически и размещается на компоненте PaintBox. При изменении положения TImage путем задания его новых координат (Left и Top) на месте начального положения остается его след. Как можно от него избавиться? Установка TImage.Visible:= False перед началом перемещения ничего не дает. Закрашивать не подходит т.к. PaintBox, являющийся фоном, имеет разные цвета и заранее не известно на каком из них (либо вообще на их границе) был размещен компонент TImage. 

Да, этот TImage не особо подходит для всяких анимаций. Он скорее годиться для размещения статических картинок. Его задача хранить в себе изображение и обновлять, по мере того как вышестоящие окна его затирают. 
   Анимация делается следующим образом. Сначала рисуется очередной кадр на невидимом битмапе (если изображение само по себе не меняется, то этот шаг пропускаем), затем очищаем область в том месте где была старая картинка (часто стирают весь фон), затем восстанавливают очищенные области (или перерисовывают весь фон заново, если стирался весь фон), затем заранее подготовленный кадр из невидимого битмапа переноситься поверх отрисованного фона.

  Если будете соблюдать указанную последовательность операций, то у вас всегда получиться красивая анимация без мерцаний, лишних следов и т.д.

  Чтобы упростить себе жизнь, можно рисовать анимацию на любом оконном компоненте и перемещать его вместо TImage. Windows сама следит за правильностью отрисовки, единственное, что потребуется так это восстанавливать картинку по обработчику OnPaint . 

затем восстанавливают очищенные области - можно об этом поподробнее? Перересовывать все нереально, поскольку объектов много и каждый из них движется сам по себе (и каждый оставляет след как показано на прилагаемом рисунке). <img src="http://s2.ipicture.ru/uploads/20120803/gVid871G.jpg" border="0">

Тут мне пришла в голову такая мысль - а может причина оставления следа это то, что родителем моего TImage является TPanel, а уже на TPanel лежит TPaintBox, на котором отрисован фон. По этому то фону и должен двигаться  TImage. Таким образом, и TImage и TPaintBox имеют общего родителя TPanel. После перемещения я и вижу на месте TImage кусочек его родителя. А вот сделать TPaintBox  родителем TImage не получается.

  Восстанавливать нужно статический фон, который был под объектом, который сместился, ну или весь фон. Все что движется и есть анимация. Не один объект, а все сразу. Лучше если их предварительно нарисовать на невидимом битмапе, а затем битмап за одну операцию нарисовать поверх фона. В этом случае не будет мерцаний. Это называется double buffer . Можно после очистки фона рисовать сразу все на фоне. Это будет чуть быстрее, но объекты будут появляться по очереди и вызывать мерцания. Кроме того рисовать нужно строго в обработчике OnPaint, иначе можно перехлестнутся с виндой, которая может сама че нить нарисовать в момент когда мы выводим изображение. 
  Следы остаются, от того, что TImage неграмотно себя перерисовывает при движении. TImage не является окном и не может ловить все нужные сообщения об отрисовки. Он перехватывает их у нижележащего окна. Где-то там на стыке код не допилен.