Yes, that's correct and it is indeed not difficult.
Having the export license as well as the "know-how" to obtain the CoO will help you when orders become bigger. So no waste here.
But that story with the shirts sounds strange.
We are ex- or importing a container a week on average. And we only deal with CoO if we (on Import) or the customer (on export) try to go for preferential Duty levels.
I also never heard of a CoO being required for a courier service. (But that doesn't mean it's impossible.)