System.Servicemodel (…) Postal code, province and city combination is not valid [Solution]

When processing orders you might come across the "System.Servicemodel (…) Postal code, province and city combination is not valid" error.

This error is shown when the Province/State Code used in an order does not match with the Postal Code, or viceversa.

Feel free to follow the step-by-step guide written below or the video guide, as you prefer:
 

NOTE: To verify if a Postal Code is valid, do not rely on user-fed/collaborative services like Google/Bing Maps, since they are prone to errors or mismatches.
For official confirmation use government-owned sources (Canada Post for Canada, USPS for USA, Royal Mail for Great Britain, etc).

To do so:

1. Find the order through any of the possible ways (after Import Orders, Batches, Order History, etc) as it applies to the case
 

2. Click the edit button of the order you wish to change

3. Change the City, Postal Code or State Code depending on the case:

4. Press Save to apply the changes

If the rest of the information in the order is correct, you will be able to process it.