Bom, isso realmente resolveu, porém também você poderia limpar a área da sua visualização, pintando tudo de uma cor só e desenhando de novo por cima. Isso também vale se você estiver usando double buffer (buffer duplo).
O paint não é o local mais adequado para você colocar a lógica de pintura. O ideal é usar escrita direta. Dê uma lida nos tutoriais do Ponto V!, são específicos para jogos: http://www.pontov.com.br/site/index.php/java/48-java2d
Também vão te explicar como montar um bom game loop, carregar imagens de forma acelerada, etc.