I wonder, is it possible to "transcode" a video source, then spit it back out in a format skype likes?

Surely there has to be something along these lines? (I mean, *nix is all about piping and manipulating streams)

You will have to create a dummy video device, with avld at http://allonlinux.free.fr/Projets/AVLD/. There may be others.

And then use mencoder or gstreamer for the transformation

gstreamer has cool effect filters.

I did that to get yuv format video from rgb format. Look at my other posts about that.