同じ問題で困ってる人がここに辿り着いて同じ方法で解決できればいいな
検索して出てくる動画にサービス削除までは載って無かったからサービスはまだ生きてる人もいるかも？

インターネットのプロパティのホームページ設定は正常だった
→IEのショートカットのプロパティのリンク先に引数は無かった
→セーフモードでIEを起動してみたらもちろん接続はできないが接続先は通常の設定通りのアドレスだった
→ユーザー固有の設定を疑いスタートアップ関連を確認
→通常起動でタスクマネージャのプロセス一覧を見るとSSFKEX.exeという知らないプロセスが起動してた
→プロセスをダンプしてみるとmysearch123のURLがマルチバイト文字列の値で見つかった
→ゴミが残っても嫌なのでこのプロセスを起動させる設定を特定できるまでは削除せずにおいておく
→全てのプログラム内のスタートアップは正常(User個別とAllUser共に)
→タスクスケジューラも正常
→msconfigのサービスにSSFKというのが表示されてた
→レジストリにもサービス関連の値にSSFK.exeを指定するものがあった
→サービス一覧にSSFKという名前のサービスが自動実行として登録されてた
→セーフモードでサービスを停止しコマンドプロンプトからサービスをアンインストール(sc.exe delete SSFK)
→通常起動でIEを起動してみて確認すると正常にホームページが表示された
→解決したのでレジストリから削除されてるのを確認
→msconfigやサービス一覧からも削除されてるのを確認
→セーフモードで起動してSSFK.exeが入っているフォルダ毎削除(この時点ではゴミ箱へ)
→通常起動でデスクトップ表示までエラーも無くIE起動も正常だったのでゴミ箱を空へ

以上です