Best design for trade or custom control process

Question

Here is the scenario.

1. company ship packages (parts) to various country
2. each country has custom rules and regulation
3. each country's custom has variety of regulatory forms (that we need to track)
4. capture when it was sent
5. capture bunch of other related data as well

Design:

1. Should I create site columns?

2. Site content type(s) with site columns?

3. Create library with "trade control" content type?

4. Question: (this list can grow over 5k in few months of use)

   a. Should I create document set for each shipment? Each shipment will have bunch of records?

   b. Should I create folder for each shipment?

   c. Should I create folder or document set per customer or per country?

What are the best design? Has anyone implement anything like this. Please i need your lesson learned and valuable input from your experience..