Data integrity across the databases of different Microservices

My question is how can I ensure data integrity between databases, that Orders table won't point to non-existent Customers?

It's a great question. There is an important dimension missing from it though, which is that of the span of time over which you wish to establish the referential integrity.

If you ask, "How can I ensure that all my data is 100% consistent at all times?" - well the answer is you can't. If you want that you will need to enforce it, either via foreign key constraints (which are unavailable across databases), or by making sure you never write to one database and not the other database outside of some distributed transaction (which is absurd and would defeat the purpose of using service orientation).

If you ask, "How can I ensure that all my data is 100% consistent after a reasonable span of time?", then there are things you can do. A common approach is to implement durable, asynchronous eventing between your services. This ensures that changes can be written locally and then dispatched remotely in a reliable, but offline manner. A further thing you can do is have a scheduled caretaker process which periodically remediates inconsistencies in your data.

However it has to be said that outside of a transaction, even over a reasonable span of time, consistency is impossible to guarantee absolutely. If absolute consistency is a requirement for your application then service orientation may not be the approach for you.