Direi di si, di solito per ovviare a ciò si fa l'intro ad un dimensione fissa (appena più piccola di 800x600) o se no si fanno due o più versioni per le diverse risoluzioni.
Ma se le immagini non sono cosi belle ed importanti puoi comunque lasciarle deformare (mettendo la qualità jpg a 100%).
O se no mettere il classico "Sito ottimizzato per 1024x768".