Optimal Storing of Cache File References with Cache Tags in MySQL

Question

Background

I've got a complex page caching system in place. Every database item that is used on a page stores a reference related to the item and the cached page. Below is the database table used to store those cached references

CREATE TABLE `sacrifice_cache` (
  `cache_id` int(21) NOT NULL AUTO_INCREMENT,
  `cache_page_id` varchar(255) NOT NULL,
  `cache_tag` varchar(100) NOT NULL,
  `cache_group` varchar(100) NOT NULL,
  `cache_expiry` datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  PRIMARY KEY (`cache_id`),
  KEY `cache_page_id` (`cache_page_id`),
  KEY `cache_tag` (`cache_tag`),
  KEY `cache_group` (`cache_group`),
  KEY `cache_expiry` (`cache_expiry`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ;

Each item tag stores a reference to the particular page cache. When it comes to the item being updated, the cache db is searched and the relevant cache files are deleted and the entries removed from the table.

Problem

Because each cached page can have many hundreds of related tags, that translates to many thousands/millions of rows to be searched. On large sites the solution really gets bogged down making updates slow.

I'm considering a different approach. Storing each cached page as a single row, but having the cache tags stored in a TEXT and then do a search for LIKE '%{item:123}%'. I'm no MySQL wizard so I'm not sure which is the best approach.

Opinions?