While trying to fix 9237, it turns out that interwiki redirects are stored in the database without their interwiki prefix. While 9237 has a patch to remove interwiki redirects entirely, it would make more sense to keep them. Looking at the database, it appears the prefix is stripped entirely from the title.
After adding a redirect from [[Test]] to [[fr:Platypus]] on my local install, the query return this:
Rd_from = 58
Rd_namespace = 0
Rd_title = Platypus
Adding this column (and making sure it's populated correctly, I'm not 100% sure where this is done), allows bug 9237 to be fixed very easily and also opens the door to something such as [[Special:InterwikiRedirects]].