I don't know if a bot is needed, but I did write a query on the SE Data Explorer that finds links to deleted posts on other SE sites.
As the screenshot shows, there were 343 such broken links on math.SE as of last weekend's SEDE update. I've fixed about a dozen of them since then, but they'll still show up in the results until the next weekly update.
The query itself is a huge mess of half-baked T-SQL, and takes several minutes to run on the math.SE database after an update. Fortunately the results are cached, so after the first slow run it becomes really quick.
FWIW, the query works by first compiling a list of all links to posts on other SE sites and then querying each site to filter out any links that point to an actual existing question or answer. The fundamental problem here is that there's no actual table containing a list of such links in the SE database (or, if there is, it's not available via SEDE) so the query has to find them the hard way, by searching through the HTML text of every single post.
This requires a whole bunch of non-trivial text processing and pattern matching, which T-SQL (at least as far as I know it) isn't really particularly good at, while being almost completely unable to make use of the its strengths as a relational database query language. The query thus spends almost all of its time laboriously searching through the full math.SE database for posts that look like they might contain links to another SE site; once it's reduced that list down to about 10,000 or so plausible candidate posts, actually extracting the links from them and checking their validity is pretty quick in comparison.
You can also use the "site switcher" on SEDE (just below the code and above the results) run the same query for other SE sites besides math.SE. For example, here's a link to the same query for MO, which currently returns 261 results. It times out if you try to run it on the Stack Overflow database, though.