This isn’t a bug, it’s just part of the Replication contract - we only replicate changes for objects that are actively being replicated. Once an object is un-parented, (i.e. removed from the DataModel, and no longer under a Replicating Service like ReplicatedStorage, Workspace, etc.), it is no longer being replicated, and future updates (i.e. the Instance being Destroy()ed), will not be replicated.
If you want the Destroy() to be replicated, you need to call Destroy() on the Instance whilst it’s still being actively replicated, i.e. when it’s still part of the DataModel as the descendant of a Replicating Service.