外部ドメインのOAuthを利用するにあたって、ユーザーからのフォーム送信に対して認可画面のリダイレクトを返す、という実装を行っていました。
それがなぜか、リダイレクトが404になってしまう自体に・・・
TL;DR
フォーム送信先で外部ドメインへリダイレクト処理を行う場合は、form_withにlocal: trueオプションをつけよう
何がおきていたか
Chromeの開発者ツールでリクエストの詳細を覗いてみると・・・
http://hogehoge.comからの302レスポンスを受け取ったあと、http://fugafuga.comに対して、OPTIONSというHTTPメソッドでリクエストを送っていることがわかりました。
fugafuga.com側ではそのURLに対するOPTIONSのルートを用意していなかったため、404エラーが発生したわけです。
CORSのpreflightが発生しているっぽい
OPTIONSは、CORSリクエストのpreflightという仕組みで使われるHTTPメソッドのようです。
参考：CORSまとめ
preflightリクエストでは、クロスドメインでAjaxリクエストを送る際に、「クロスドメインだけど、このページからリクエスト送っていいかい？」と確認をとるやりとりが発生します。
また、preflightリクエストを送るかどうかはHTTPの仕様に則ったブラウザの判断なので、原則、開発者が直接操作はできません。
リダイレクトにCORSの仕組みが適用されている？？
上述の通り、CORSはAjax等でクロスドメイン通信する場合に適用される仕組みであり、今回のように302レスポンスでリダイレクトされる場合にpreflightリクエストが発生するのはおかしい。
これが今回の主なハマりポイントで、かつ、解決の糸口でした。
原因は、フォーム送信時のAjaxリクエスト
rails5.1のform_withを使用して今回のリクエストフォームを生成していました。
全く意識せず実装していたのですが、form_withはデフォルトで、フォーム送信にAjaxを用いるようです。（form_tagにremote: trueを指定した状態）
参考：【Rails 5】(新) form_with と (旧) form_tag, form_for の違い
おそらく、ブラウザは以下のような振る舞いを行っていたものと思われます。
submitボタン押下に対し、Ajaxで`http://hogehoge.com`へPOSTリクエストを送る
↓
そのレスポンスとして、`http://fugafuga.com`への302リダイレクトを受け取る
↓
リダイレクト先へのリクエストもAjaxで送信しようとする（クロスドメインのためpreflightリクエストが発生する）
フォーム送信に対して外部URLのリダイレクトをする場合はAjaxを使わせない
form_withのAjaxリクエストは、
以下のように、local: trueオプションをつけることで回避（通常のSubmitさせる）可能です。
= form_with model: @hoge, url: tip_new_path, method: :post do |f|
補足：turbolinksを使っていれば回避可能
この問題、実はturbolinksを動かした状態だと発生しません。
turbolinksの効いている状態でいろいろと調べてみたところ、
- redirect_to で、status: 200の状態でJavaScriptのコードをレスポンス
- ブラウザで↑のJSを実行してリダイレクト
という挙動をしていました。