Cual seria la solución mas efectiva para redimencionar una imagen sin que pierda calidad?

Redimencionar para reducir tamaño no tiene problema, el problema es cuando necesitas aumentar el tamaño ya que el software intenta completar la información faltante con los pixeles que hay al rededor. Con imágenes de mapas de bits siempre va a pasar eso.

Tal cual como lo expica @gollum23. Quiero complementar que en photoshop hay una opción llamada objeto inteligente o Smart objet , al convertir los mapas de bits en esto podrás escalar cuantas veces necesites (además de otras muchas otras ventajas) sin que pierda calidad, pero teniendo en cuenta lo que dice Gollum sobre sobredimensionar más allá del tamaño original