address does not exist error (Omnyfy integration)

We see an error message "Address does not exist" in our Omnyfy integrated website.

It used to show rates when we used Sandbox token, but with production token we getting this error

In the log file on Omnyfy we see the records like that:
Additional information we have found in Easyship API log, error looks like:

2021-04-02T23:32:51+00:00 INFO (6): {"origin_address_id":"3b9d6a71-XXXXX","origin_postal_code":"3076","origin_country_alpha2":"AU","destination_postal_code":"3000","destination_country_alpha2":"AU","destination_city":"MELBOURNE","destination_address_line_1":"101 Collins Street","taxes_duties_paid_by":"Sender","is_insured":"true","output_currency":"AUD","items":[{"actual_weight":"2.0000","height":"27","width":"22","length":"31","category":"dry_food_supplements","declared_currency":"AUD","declared_customs_value":3.9,"quantity":1}]}
2021-04-02T23:32:51+00:00 INFO (6): {"message":"Address does not exist"}

Note I've changed the characters origin_address_id for confidentiality