[Busco SUGERENCIAS] Redimensionar imagenes de una página Web

[TIaGoX]

Efectivamente es capricho del cliente, por otro lado el ancho varía desde un cierto ancho mínimo (que se adaptaría a una resolución de 800x600) hasta un máximo que para resoluciones mas grandes, pero no ocupa toda la pantalla. Entiendo lo que ustedes me dicen del ancho fijo, pero no me parece que sea algo imposible. Ya que navegadores como Firefox 3, Safari y Opera; se preocupan un poco mas por la calidad de las imágenes y hacen que estas redimencionen sin ningun problema. El tema es con los navegadores mas antiguos, o con el clasico y querido (mentira) Internet Explorer

Ademas el problema solo pasa con el header de la pagina y con los botones del menú, que son imágenes en las cuales hay texto. Eso podría solucionarse con un poco de Flash, pero eso tampoco me lo permite el cliente.

Saludos, y muchas gracias por las respuestas.