Perfect Resize bör kunna hjälpa en bit på vägen. Har själv inte provat mjukvaran, men enligt utsaga så använder den en fraktalalgoritm för att ge ett mycket bättre resultat än det du uppnår genom att skala om i valfri bildredigerare.
Alltid värt att prova... berätta för mig hur det funkade sen, jag har varit lite nyfiken på om det är nåt att ha.