Laravel Queueはlistenのコマンドを常時走らせる事によって、メール等を非同期で送信することができる。
その際に、今まで普通に動いていたのに、いつの間にか突然下記のようなエラーが出てきた。
[InvalidArgumentException] No handler registered for command [__PHP_Incomplete_Class]

ドキュメントを見ると、
アプリケーション内でオブジェクトをシリアライズして再利用する場合のお勧めは、そのクラスの定義をアプリケーション全体で include することです。クラスの定義が存在しなければオブジェクトの復元に失敗してしまいます。その場合、PHP は __PHP_Incomplete_Class_Name クラスのオブジェクトを返します。このオブジェクトにはメソッドは一切なく、使い道がなくなってしまいます。
http://php.net/manual/ja/language.oop5.serialization.php

ということで、クラスを生成できなかったのが問題ということのよう。

いろいろ調べた結果、jobの定義しているクラスのnamespaceの大文字小文字の問題だったよう
phpcsを使っていると、

App\Jobs\Hoge
↓
app\Jobs\Hoge

に変更を促されるが、jobをfireしているクラスでは
namespace Illuminate\Queue;
であり、app\Jobs\Hogeを展開しようとすると
Illuminate\Queue\app\Jobs\Hoge
を展開しようとしてエラーが出るよう。

composer.jsonでは、App\
をpsr4読みしているので、基本的にAppを使うようにしたほうがいいみたい。