Until today, I was always under the impression that Maxim Stepin's hq4x was the state of the art in upscaling algorithms for sprites and other pixel art. Backed by Microsoft Research, Kopf and Lischinski's algorithm published in SIGGRAPH 2011 yields even better results, scaling past 4:1 and beyond.