You can make your own fancy stationery very easily if you have a sewing machine. And I don't mean by stitching on the paper, because that is not easy/can gum up your machine. I mean by perforating the edges in pretty patterns!
Just set your machine to one of the pre-set fancy stitches, and send your paper on through! Do some testing first on scrap paper because, as you can see on the envelope in the picture, some stitches are too close together and tear the paper.
Of course you can also do fancier things by disengaging the feed dogs on the machine and doing a little freehand sewing, too.
Sewing-machine perforations can also give you the easy-tear functionality of perforated paper.
If you're writing a letter, this looks great in a hand-stitched envelope.