Sync'ing deleted items across multiple devices

[blmiles]

First, I'll say sync is working perfectly when adding and editing any records on multiple devices.
I can go from an Android device to an iOS device then a Windows app and all works well across the board.

However, deleting any record on one device, does not cause that item to be removed on the other devices when sync occurs.

I use the [DbSet].Remove(item); method and that removes the item on device1, the app syncs with the online db. Item is removed.

If I then start app on device2 and the app syncs with online db, the initial push fails as it can no longer find the record that was deleted on device1 and consequently does not remove the record from device2.

Maybe I have not wired this up correctly to handle deletes across devices.
I thought that deleting is always a soft delete and one can check/filter on the .Deleted property on any item.

Maybe I need to do a Pull first when app starts up. Then do the normal push/pull sync while app is in use.
Problem with that is users don't necessarily kill the app between uses but the app does sync after any change on a record.
Or a date/time check, if app inactive for a given period, pull first (since any changes would have already been sync'd in last use) then again, regular push/pull.

Any advice would be welcome.

Maui app, targeting multiple device platforms.