Add noise to video while maintaining compressibility I'm creating a promotion video that has to be uploaded to YouTube and Vimeo.

In post-production (using Final Cut), I've added a noise for aesthetic purposes.

This noise looks really bad on YouTube and Vimeo because these sites compress the video's you upload to them.

I know that (pseudo-)random noise is very hard to compress (almost by definition), so I was wondering if there exist noise filters that visually 
seem random but are in fact not random, making compression on them easier and hopefully improving Youtube and Vimeo quality?
As you say, noise by definition doesn't compress well. You can try different types of noise in FCP. The Add Noise filter has several choices - Gaussian is a reasonable simulation of film grain, but you can try the other choices, too. They might compress better (or worse). 

But your best bet is to increase the data rate of the resulting file. I don't know the limitations of YouTube or Vimeo, and your content may make it difficult to stay within their limits, but that's probably going to get you better results than trying to find some form of noise that isn't (as) affected by compression.