Paperway normally sells regular C5s, but not windowed ones, but they were sold out anyway.

Most envelopes don’t come in “A” sizes (not even the ones that claim to!) because that’d be silly. You can’t fit an A4 sheet of paper into an A4-sized envelope, on account of it being the same size! Instead, enevlopes for holding whole unfolded A4 sheets are called C4 envelopes, and they’re just a little bit bigger. A C5 envelope is just a little bigger than an A5 sheet of paper, and is the same size as most bills come in. DL envelopes (size D, Letter) are the “fold-an-A4-sheet-three-times” size envelopes you see a lot of.

So as you see, a C5 envelope isn’t really that exotic a request (I got some from Woolworths in the end), but apparently C5 envelopes with windows are, somwhow.