Удаление одной строки из большой таблицы MySql приводит к «таймауту блокировки»

Я использую MySql 5.0.22 и у меня действительно громоздкая таблица, содержащая примерно 5 миллионов строк.

Некоторые, но не все строки ссылаются внешним ключом на другую таблицу.

Все попытки отбросить строки, на которые нет ссылок, до сих пор терпели неудачу, каждый раз приводя к тайм-аутам блокировки.

Копирование строк, которые я хочу, в альтернативную таблицу также не удалось из-за тайм-аута блокировки.

Подозрительно, даже утверждение, которое должно закончиться мгновенно, как показано ниже, также потерпит неудачу с «тайм-аутом блокировки»:

DELETE FROM mytable WHERE uid_pk = 1 LIMIT 1;

... именно в этот момент у меня закончились идеи.

Редактировать: Что бы это ни стоило, я работал над этим на моей системе разработки, поэтому только я фактически использую базу данных в данный момент, поэтому не должно быть никакой блокировки вне SQL работает.

У кого-нибудь из гуру MySql есть предложения о том, как приручить эту мошенническую таблицу?

Правка № 2: По запросу структура таблицы:

CREATE TABLE `tunknowncustomer` (
  `UID_PK` int(11) NOT NULL auto_increment,
  `UNKNOWNCUSTOMERGUID` varchar(36) NOT NULL,
  `CREATIONDATE` datetime NOT NULL,
  `EMAIL` varchar(100) default NULL,
  `CUSTOMERUID` int(11) default NULL,
  PRIMARY KEY  (`UID_PK`),
  KEY `IUNKNOWCUST_CUID` (`CUSTOMERUID`),
  KEY `IUNKNOWCUST_UCGUID` (`UNKNOWNCUSTOMERGUID`),
  CONSTRAINT `tunknowncustomer_ibfk_1` FOREIGN KEY (`CUSTOMERUID`) REFERENCES `tcustomer` (`UID_PK`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8$

Примечание, при попытке удалить FK также тайм-аут.