Imperous1) мы можем одним запросом из базы выбрать всю информацию по клиенту. (легкость сохранности, целостности и получения всей инфы)
2) если мы грохаем клиента, то каскадно удаляется вся информация. (нет "мусора")

Я так понимаю, что должен быть механизм, который:
1) находит несвязанные данные
2) убирает мусор

Но как же на самом деле решается вопрос целостности информации в распределенных БД, которые закреплены за своим микросервисом?
В общем случае не существует никакой связи между сервисом и БД.
Более того. Информация о внутреннем устройстве сервиса может быть неизвестной
или засекреченной (какой-то банковский сервис).

Для тебя как для разработчика данного микросервиса существуют такие шаблоны как
- CQRS (это больше относится к дизайну приложения в целом но этот шаблон
отказыватся от согласованности в пользу производительности. Грубо говоря команда
и запрос вообще работают с РАЗНЫМИ БД. Это постулировано в презентациях по СиКюРэС.
Например для команд могу юзать EventStore системы а для отчотов какие-то RDBMS)
- OLTP/DWH БД. Обращения опер-дня идут в одну базу. А аналитика или исторические
данные - из другой. Между ними есть некая задержка во времени. И само приложение
(в данном случае микросервис) должно понимать куда смотреть. Как вариант просто
брать текущую дату и роутить запросы в разные направления)
- Мастер и реплика. Основная и резервная.

Твой вопрос касаемо нарушения согласованности между БД. Почитай про теорему Эрика Брювера.
В частности например AP (Availability+Partition tolerance). Это нарушение присутствует в интернете
везде. В частности серверы DNS никода не достигают 100% consistency но им это не надо. Протокол
использования DNS позволяет нам читать и видеть устаревшие записи и не испытывать особых проблем.

По твоему алгоритму уборки мусора мне нечего сказать. Я не понимаю как ты посчитал какие-то данные
мусором. Это мне кажется задача совершенно другая и не имеющая отношения к основной работе
микросервиса. Может удаление исторических данных. Может удаление childs without parents.

В общем случае не существует никакой связи между сервисом и БД.
Неверно выразился. Нет взаимного соответствия между сервисом и БД.
Может быть сервис вообще без БД. И может быть сервис с множеством БД.
И могут 2 сервиса ходить в одну БД.