I need to do some additional testing (due to how destructive this operation can be), but initial testing seems to indicate that running wp_cache_flush() immediately after the deletion does indeed fix the problem.
Thanks a bunch, hopefully that’s all it needed!