How I felt not having square origami paper as a kid.
(It's okay, I learned immediately how to rectify, uh, squarify, the situation.)
I sort of had the same issue, eventually went to a small local printing company. They had loads of scrap paper in all possible colours. They were very nice to me (I was a kid so that helps I guess), and I got a load of scrap paper for free. They even cut a lot of it in square size. This supply lasted me for many many years of folding pleasure.
Yeah, it is easy to try to correct the situation as an adult afterwards. This was just an account of my feelings then.
And as I mentioned below - maybe exactly this was in the way from making the best paper plane ever, that could fly all the way to my neighbour? What did I know?