Parecchio tempo fa, ebbi modo di confrontarmi con un problema simile nello scrivere una GUI che si basava su Allegro. La soluzione che adottai non era quella di riscrivere tutto lo sfondo ma di memorizzare, in un'apposita struttura dati, solo la parte di schermo al di sotto della finestra in uso. Per cui ogni volta che spostavo la finestra eseguivo il seguente pseudocodice in loop :
codice:
- scrivi sullo schermo la parte di schermo memorizzata precedentemente
- leggi le coordinate del mouse
- memorizza la porzione di schermo che ha come angolo sinistro alto le coordinate 
  del mouse e grandezza pari alla finestra.
- riscrivi la finestra (o nel tuo caso il rettangolo) sullo schermo
Ovviamente nel far questo devi crearti delle strutture dati apposite per memorizzare la posizione del rettangolo, il puntatore alla bitmap che rappresenta la porzione di schermo memorizzata, etc. Saluti