I don't see watermark or compositing functionality in On2 Flix Pro and Macromedia/Adobe Video Encoder. I did read this weekend in the latest release of Premiere Pro C3 you can directly output Flash video. If this is the case then you could easily use Premiere Pro CS3 to watermark the video.
I don't know of any way to do this on the fly, server-side. It would require that the video be decoded and re-encoded on the server. This is very expensive in both memory and CPU.