My only thought on this is that as long as you're scaling "inward"
(compressing) to fix a distortion then no artifacts are made.  But
anywhere where the distortion fix stretches outward then artifacts are made.

I don't know if for a fisheye that distortion fixes employ both, eg:
parts of the scene compress and other stretch to linearize the image.
If stretching is involved, then the overall image will have to be
downsampled to eliminate any 'stretch marks' in the image.   

I received the following bit of spam the other day, maybe it can be of
use to you: http://www.imagetrendsinc.com/ There's a free trial.  I have
no idea if it is any good.

Obviously a tilt-shift lens would be best, but in the Canon tilt-shift
lens I believe that also clips part of the image (??).

G'luck!

Alan.

I am increasingly of the Photoshop-fixes-everything persuasion: what the
picture looks like at the end is all that counts, not how you get there.
It is problematic to correct for all the distortion that a fisheye
introduces although there are programs and plug-ins that claim to do so.
However it is not difficult to correct for keystoning of architectural
subjects. Most often correction in more than one direction/dimension is
required but with practice this becomes less difficult.
It is important to include enough background in the original image because
of the cropping that will be necessary.
I do not see how making these corrections in Photoshop is any less valid
than making them with swings and tilts on the film plane.
People have to shed the mentality of how things were done prior to the
availability of digital tools. Swings/tilts, PC lenses are great but not the
only way to accomplish things.

I've never used a fisheye but correct perspective and WA barrel distortion
as a matter of course with Photoshop.
http://www.pbase.com/stanmore/image/72147131/original is a good example. If
I could afford a Canon 24mm TS lens I would get one because it would let me
compose 'perfectly' at capture
--
Simon

You can fix perspective keystone distortion using Photoshop. I have
some tips on my web site showing several ways to do this.
You can also fix warp distortion as is caused by fisheye and
rotating panorama cameras using the free plugin Panorama Tools.
I show how this is done using cylindrical projections as well, to
correct spherical distortion the steps are the same you just pick
different options within the plugin.

It is also possible to approximate the shift in the plane of sharpness
which a tilting lens can perform. One uses a wide angle lens and tilts
the whole camera to bring the desired plane into focus. This shifts
the image to the edge of the frame. Then one crops out the portion
needed and makes any perspective adjustments. This is not exactly
the same as tilting only the lens and needs more magnification to
get to the same final size, but it is better than nothing.

I haven't tried it, but I'sd suspect that once you correct the
distortion and then crop the resulting pincushion-shaped image to a
rectangle, you'd get effectively the same picture as a 21 or perhaps
even 24mm corrected lens.

It isn't actually necessary to use a shift lens; all they do is crop the
image circle differently by moving the image centre away from the frame
centre. You can get the same effect by using a high enough resolution
sensor or film and then cropping out the unwanted forground in
photoshop/on the enlarger. Sure you lose some resolution but if you have
plenty to start with, then you might be able to afford it.