I'm not sure if this is still the case, but in CS3 & CS4, Photoshop used 2 different algorithms for scaling. one was a much nicer scaling (used for slight enlargements), but took a lot longer to render, and the other was faster (for huge enlargements) but didnt' provide as good of results.
I had a customer who made an action in PS to enlarge by 8%, which would use the better algorithm, and run it several times until he got close to the size he needed. it seemed to provide pretty good results.