封筒だけなら、昔アルバイトしていたコンビニでも置いていました。
発送するには郵便局の窓口に持っていかなくてはなりませんけども。
たしか切手や印紙などと同じ扱いだったので、そういうものを置いて
いる文房具店なら現金書留用封筒もあるかもしれません。