While crushes took place no delete for table "users" was done. At least it wasn't the trigger. I guess the problem is the foreign key check with the (probably) key failure and then kind of internal rollback/ignore for the "not matching the key" query. Execution of "on delete cascade" is NOT a reason, I'm 99.9% sure.
And at the same time there is a bunch of other tables with foreign keys, no problems (except it seems like integrity constraints like "on delete cascade" sometimes do not work and produce "zimbie" records, but I still can't understand how exactly that happens).
And this problem arised with time, all was fine until the table grow to 80M of rows. Do you have a really LARGE table in the lab?

Here comes "users":

| users | CREATE TABLE `users` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `login` varchar(100) DEFAULT NULL,
  `pwd` varchar(100) DEFAULT NULL,
  `s_mail` varchar(50) DEFAULT NULL,
  `s_www` varchar(255) DEFAULT NULL,
  `s_inn` varchar(50) DEFAULT NULL,
  `s_descr` text,
  `s_phone` varchar(100) DEFAULT NULL,
  `offert_accepted` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `s_full_name` varchar(255) DEFAULT NULL,
  `s_first_name` varchar(100) DEFAULT NULL,
  `s_middle_name` varchar(100) DEFAULT NULL,
  `s_last_name` varchar(100) DEFAULT NULL,
  `s_city` varchar(100) DEFAULT NULL,
  `s_address` varchar(255) DEFAULT NULL,
  `last_used` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `last_host_id` smallint(5) unsigned DEFAULT NULL,
  `mail_confirmed` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `msisdn_confirmed` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `msisdn_confirm_code` varchar(4) DEFAULT NULL,
  `msisdn_req_time` datetime DEFAULT NULL,
  `java_phone_model` varchar(30) DEFAULT NULL,
  `java_font` varchar(30) DEFAULT NULL,
  `java_safe_mode` tinyint(4) NOT NULL DEFAULT '0',
  `user_pic` varchar(16) DEFAULT NULL,
  `denied_libs` varchar(255) DEFAULT NULL,
  `recenser_type` int(11) DEFAULT NULL,
  `partner_id` int(11) DEFAULT NULL,
  `creat_date` datetime DEFAULT NULL,
  `partner` int(10) unsigned DEFAULT NULL,
  `partner_valid_till` date DEFAULT NULL,
  `partner_pin` int(10) unsigned DEFAULT NULL,
  `account` decimal(9,2) NOT NULL DEFAULT '0.00',
  `abonement_start` datetime DEFAULT NULL,
  `abonement_expires` date NOT NULL DEFAULT '2006-01-01',
  `abonement_period` smallint(6) DEFAULT NULL,
  `abonement_delay` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `abonement_max_price` decimal(6,2) DEFAULT NULL,
  `abonement_downloads` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `abonement_left_clicks` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `abonement_left_summ` decimal(6,2) DEFAULT NULL,
  `user_pic_height` tinyint(3) unsigned DEFAULT NULL,
  `user_pic_width` tinyint(3) unsigned DEFAULT NULL,
  `show_pay_btn` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `s_puid` varchar(255) DEFAULT NULL,
  `discount` decimal(4,4) NOT NULL DEFAULT '0.0000',
  `money_bonus` decimal(9,2) NOT NULL DEFAULT '0.00',
  `subscr_last_reminded` datetime DEFAULT NULL,
  `subscr_free_arts_given` datetime DEFAULT NULL,
  `subscr_type` tinyint(3) unsigned NOT NULL DEFAULT '2',
  `subscr_period` tinyint(3) unsigned DEFAULT '1',
  `subscr_content` tinyint(3) unsigned DEFAULT '2',
  `subscr_genres` text,
  `s_subscr_text_authors` text,
  `subscr_date` timestamp NOT NULL DEFAULT '0000-00-00 00:00:00',
  `s_subscr_text_pattern` text,
  `subscr_languages` text,
  `prefered_currency` char(3) DEFAULT NULL,
  `last_paymethod` tinyint(3) unsigned DEFAULT NULL,
  `utc_offset` char(6) DEFAULT NULL,
  `last_ip` varchar(15) DEFAULT NULL,
  `socnet_last_reminded` datetime DEFAULT '0000-01-01 00:00:00',
  `moved_from` smallint(5) unsigned DEFAULT NULL,
  `moved_to` smallint(5) unsigned DEFAULT NULL,
  `subscribe_new_buys` tinyint(1) NOT NULL DEFAULT '1',
  PRIMARY KEY (`id`),
  UNIQUE KEY `login` (`login`),
  KEY `s_mail` (`s_mail`),
  KEY `partner` (`partner`),
  KEY `partner_valid_till` (`partner_valid_till`),
  KEY `abonement_expires` (`abonement_expires`,`abonement_left_clicks`),
  KEY `puid` (`s_puid`),
  KEY `s_phone` (`s_phone`)
) ENGINE=InnoDB AUTO_INCREMENT=14571504 DEFAULT CHARSET=utf8 |

And I do not quite understand "NULL key skipped" message. Key columns in the insert are NOT null:

130210 13:21:06 [Note] WSREP: NULL key skipped: INSERT IGNORE INTO users VALUES ('14214700','iph9027E4342B35','<skipped for security reasons>','','',NULL,NULL,'','0','  ','','','','',NULL,'2013-02-10 13:21:06','1965','0','0',NULL,NULL,NULL,NULL,'0',NULL,NULL,NULL,NULL,'2013-02-10 13:21:06',NULL,NULL,NULL,'0.00',NULL,'2006-01-01',NULL,'0',NULL,'0','0',NULL,NULL,NULL,'0',NULL,'0.0000','0.00','2012-08-10 13:21:06',NULL,'2','1','2',NULL,NULL,'0000-00-00 00:00:00',NULL,NULL,NULL,NULL,NULL,NULL,'0000-01-01 00:00:00',NULL,NULL,'1')