外键约束在现有键上失败

在现有的Laravel项目中，我们在mysql数据库中插入新记录时遇到了一个模糊的问题。工作流程是这样的，每当我们创建一个新公司时，我们也会创建属于该公司的用户，不知何故，在提交新用户时，外键约束失败，而我们100%确定密钥存在，并且我们手中有正确的密钥。

更奇怪的是，有时创建得很顺利，之后我们可以插入许多用户，而不会出现任何问题。

我希望有人能为我指明正确的方向，告诉我如何进一步进行或调试。

编辑：我添加了一些代码，我认为这里没有什么特别的地方，除了foreignkey上可以为null的部分。这是一个相对较新的添加，因为不是每个用户都属于一家公司，所以这就是我添加该用户的原因。

我认为问题是：当你知道（验证）这个密钥存在，是正确的密钥，并且100%确定是正确的类型时，外键怎么会失败。

    $company = new Company();
    $company->fill($request->all());
    $company->showLicence = (int)$request->get('showLicence');
    $company->save();
    //create a zero-user for each company to be able to login support    staff
    $user = new User();
    $user->name = "user";
    $user->password = bcrypt('password');
    $user->company_id = $company->id;
    $user->save();
//user migration
Schema::create('users', function (Blueprint $table) {
        $table->increments('id');
        $table->string('name');
        $table->string('email')->unique();
        $table->string('password', 60);
        $table->rememberToken();
        $table->timestamps();
        $table->string('profession');
        $table->integer('productivity');
        $table->date('birthDay');
        $table->boolean('active');
        $table->string('standardCalendar');
        $table->string('calendar');
        $table->integer('department')->unsigned();
        $table->integer('company_id')->unsigned()->nullable();
        $table->foreign('company_id')
            ->references('id')
            ->on('users')
            ->onDelete('cascade');
    });
    Schema::create('companies', function (Blueprint $table) {
        $table->increments('id');
        $table->timestamps();
        $table->string('companyName');
        $table->string('street');
        $table->string('zipcode');
        $table->string('city');
        $table->string('phone');
        $table->string('fax');
        $table->string('email');
        $table->string('website');
        $table->string('logo');
        $table->string('taxNumber');
        $table->string('welcome');
        $table->boolean('showLicence');
    });