MySQL Error Number: 1452 (unusual case)

Question

I tried adding a Foreign Key using this query:

ALTER TABLE `StripeBilling`
        ADD CONSTRAINT `StripeBillingPatientRef`
         FOREIGN KEY (PatientRef)
          REFERENCES `Patient`(`PatientId`)
            ON DELETE SET NULL;

My tables mysql_dump is:

CREATE TABLE IF NOT EXISTS `StripeBilling` (
  ...
  `PatientRef` int(10) unsigned DEFAULT NULL,
  ...
) ENGINE=InnoDB AUTO_INCREMENT=10000000 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
ALTER TABLE `StripeBilling`
  ADD PRIMARY KEY (`StripeBillingId`), ADD KEY `StripeBillingAgentRef` (`AgentRef`), ADD KEY `PatientRef` (`PatientRef`);
ALTER TABLE `StripeBilling`
  MODIFY `StripeBillingId` int(11) NOT NULL AUTO_INCREMENT,AUTO_INCREMENT=10000000;
ALTER TABLE `StripeBilling`
ADD CONSTRAINT `StripeBillingAgentRef` FOREIGN KEY (`AgentRef`) REFERENCES `Agent` (`AgentId`) ON DELETE SET NULL;

And patient's table is:

CREATE TABLE IF NOT EXISTS `Patient` (
  `PatientId` int(10) unsigned NOT NULL,
  ...
) ENGINE=InnoDB AUTO_INCREMENT=10000000 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
ALTER TABLE `Patient`
  ADD PRIMARY KEY (`PatientId`), ADD UNIQUE KEY `PatientSerial` (`PatientSerial`);
ALTER TABLE `Patient`
  MODIFY `PatientId` int(10) unsigned NOT NULL AUTO_INCREMENT,AUTO_INCREMENT=10000000;

But MySQL returns an error:

Cannot add or update a child row: a foreign key constraint fails (newportal_enc.#sql-3863_9f, CONSTRAINT StripeBillingPatientRef FOREIGN KEY (PatientRef) REFERENCES Patient (PatientId) ON DELETE SET NULL)

I'm confused because table newportal_enc.#sql-3863_9f does not exist in my database.

This is not due to the presence of the PatientRef index, becouse after removing of this index my issue still exists.

Why am I getting this error and how can I solve it?