VirtualDub puede hacerlo, ademas con filtros tipo Bilinear y tal...
Pero tendras que recomprimir, claro :p
Todo esta en Video>Filters, Resize y en lugar del Filter Mode: Nearest Neighbour, pues ponle el bilinear o Precise Bilinear, o prueba con los otros modos para ver cual te convence mas.
Saludos!