Query takes 17 seconds, suggestions needed

[Ondernemer]

I am building a website which stores the headers of newsgroup articles in a
database so people can search through the headers using keywords.

My queries use WHERE LIKE statements.

CREATE TABLE `headers` (
`header_id` int(11) NOT NULL auto_increment,
`header_num` int(11) NOT NULL default '0',
`message_id` varchar(150) NOT NULL default '',
`subject` varchar(200) NOT NULL default '',
`poster` varchar(75) NOT NULL default '',
`postdate` int(11) default NULL,
`newsgroup` varchar(100) NOT NULL default '',
`partnum` int(11) NOT NULL default '0',
`parttotal` int(11) NOT NULL default '0',
`numlines` int(11) NOT NULL default '0',
`bytes` int(11) NOT NULL default '0',
`date_added` timestamp(14) NOT NULL,
`sortfield` varchar(200) NOT NULL default '',
PRIMARY KEY (`header_id`)
) TYPE=MyISAM

The SORTFIELD column is a string, made up of SUBJECT. Using RegExps I cut
off things like RE: so that I can group similar subjects and sort on that
field.

Currently I have 5 million records in this table and searching the table
takes 17 seconds to generate an output.

I have tried using FULLTEXT indexes but I dropped this because FULLTEXT does
not allow partial searches e.g. wildcard-searches.

How can I speed up my results? I'm very much in the dark here. I want the
user to be able to do a GLOBAL search and not limit them by making them
select the newsgroup to search in before they submit theit keywords.

Any help would be very much appreciated.