これで何時間費やしたことか、、

考えてみれば当然で、WPのnonceは一定時間で破棄される識別子で、これは時刻、アクション名、ユーザーID、セッショントークンから生成されている。
そのためログアウトすると無事にwp_verify_nonceが通るようになる(実装前にログインしていれば、失敗し、一度ログアウトすれば通る)。