どういうタイミングで変更前の%postname%を格納してるか気になったのでデータベースを見た。
Disable Revisions and Autosaveプラグインを使っていることと、自分がパーマリンクに%postname%を使用していないので、他とは動きは違うかもしれないが一応自分メモ。
だから他の人はなんの参考にもならないと思います。
データベースをわからないのに直接いじったりしてたから、すでに壊れてるかもしれないし。

レコードはwp_postmetaテーブルに作られる。

meta_id
bigint(20) unsigned 連番
プライマリキーでオートインクリメント

post_id
bigint(20) unsigned [0]
wp_postsテーブルのプライマリキー参照

meta_key
varchar(255) NULL
カスタムフィールドのキー名

meta_value
longtext NULL
カスタムフィールドの値

レコードはmeta_keyの値”_wp_old_slug”として作られる。

【新規投稿時のスラッグの変更】
・新規投稿時にスラッグを変更した場合、wp_postmetaテーブルに_wp_old_slugのレコードは追加されない。

・新規投稿時にスラッグを変更しなかった場合、wp_postmetaテーブルには_wp_old_slugのレコードは追加されない。

【投稿編集時のスラッグの変更】
・そのスラッグがwp_postmetaテーブルをpost_id+meta_key（=_wp_old_slug）+meta_value（=変更するスラッグ値）で検索して無かったらレコードを追加する。

【N回スラッグを「違う値」で付け替えた場合】
・新規投稿時にスラッグを変更した場合はN-1個のレコードが追加される。初期値の記事タイトルはwp_old_slugのレコードは作られない。

・新規投稿時には編集せず編集時に変更した場合はN個のレコードが追加される。初期値の記事タイトルはwp_old_slugのレコードは作られる。

【以前に付けた同じスラッグに変更した場合】
・変更前のレコードを追加し、同じ値のレコードを「削除」する。

スラッグを　”テスト”→test1→test2→test1→test3と変更したら
（”テスト”はパーセントエンコーディングされてる）

（新規投稿時に変更した場合）
1回目にtest1に変更　
2回目にtest2に変更　test1
3回目にtest1に変更　test2
4回目にtest3に変更　test1　test2

（新規投稿時に変更しなかった場合）
1回目にtest1に変更　テスト
2回目にtest2に変更　test1　テスト
3回目にtest1に変更　test2　テスト
4回目にtest3に変更　test1　test2　テスト

だらだらと書いたけど要はwp_postmetaテーブルとwp_postsテーブルに無いスラッグがwp_postmetaテーブルに追加される。
ちゃんとやってるんですね。
リダイレクト処理とはまた別かもしれないけど、データベースに格納されている変更前のスラッグのデータはこのように追加される、と思います。

だから%postname%を決めて設定する時は、新規投稿時にスラッグを設定した方が、不要な記事タイトルのレコードがwp_postmetaに追加されないです。（上の場合では、テスト）

自分の場合は、後で一括してスラッグを連番で変更したので、wp_postnameには変更前の記事タイトルが入っていた。
パーマリンクは%postname%は使わず、年月日時間秒のみにしている。
だから自分はwp_old_slugは使わないので、Adminerを使ってwp_postmetaテーブルから全部削除した。
テーブルのインデックステーブル？はmeta_id+post_id+meta_keyとなってる。
たぶんデータを削除したら自動でインデックスは貼り直すと思うんだけど、そこはまだよくわかりません。
削除、追加はwp_postmetaテーブルを参照しているテーブルが無いので、大丈夫な気がする。
最悪、後でどうしても必要だったらINSERTすればいいかと思ってやりました。

最後にこれはデータベースのデータを見ただけで、WordPressがどういう動きをするか、Googleがどう見てるかは全然考えてません。
もしかしたら_wp_old_slugはあっても全然見てないかもしれないし。
ただwp_postmetaテーブルの溜まったデータを削除する時には参考になるかもしれません。
また、もし_wp_old_slugを見てたなら、リダイレクトがうまくいかなかったりした時は、一括でUPDATEしたりDELETEしたりできるかもですね。

あとデータベースを直接いじる場合は、データベースのバックアップは忘れないように。
SELECTするだけで更新、削除しないから大丈夫って思うかもしれないけど、手元が滑ったりして削除ボタンを押してしまったら大変だし、Adminerなどの管理ツールは意外にあっさり実行するから気をつけること。
これを書いた私はWordPressもPHPもHTMLもデータベースもなんにもわかってないので参考にはなりませんけど、バックアップだけはやって下さい。