プロジェクトの開発環境ではvagrant + chefでプロビジョニングしてるんですが、先日どうにもvirtualboxの調子が悪くなってしまいました。
状態として、仮想マシンが2つになったり（マシン名に付与される数値は違う）起動中のまま固まったりで。
結論から言いますと、virtualboxのver4.3.20からver4.3.12にダウングレードし、以下の手順を実行しました。
要するに、ver4.3.12に再インストールした後で、仮想マシン起動時にE_FAILが返ってくる場合、再度ver4.3.12のインストーラを起動し、repairを選択します。
ちなみに、ここでremove⇒再インストールを延々繰り返しても一向に解決しませんでした。
取りあえず上記手順で解決しましたが、ver4.3.20（2014/12/12時点での最新）はまだ様子見です。