Erratic performance for a specific query in MySQL

I have two job queues doing complimentary work and writing their output
once a minute into a file. The files for each minute have to processed
in pairs - one from the first job queue and one from the second and the
results are merged and delivered to the final client. The filename and
other details of these files go in to a MySQL database - a different
table for each job queue.
The merging process has to read the two files for that minute from the
two tables joining on a file id. Here is MySQL schema I am using:

CREATE TABLE `Job_Queue_1` (
`FileID` varchar(64) NOT NULL default '',
`File_Path` text NOT NULL,
`File_TimeStamp` bigint(12) NOT NULL default '0',
`Process_Status` char(1) NOT NULL default '',
PRIMARY KEY (`FileID`),
KEY `Process_Status` (`Process_Status`,`File_TimeStamp`)
) ENGINE=InnoDB


CREATE TABLE `Job_Queue_2` (
`FileID` varchar(64) NOT NULL default '',
`File_Path` text NOT NULL,
`File_TimeStamp` bigint(12) NOT NULL default '0',
`Process_Status` char(1) NOT NULL default '',
PRIMARY KEY (`FileID`),
KEY `Process_Status` (`Process_Status`,`File_TimeStamp`)
) ENGINE=InnoDB

File_TimeStamp is an integer representing the time as YYYYMMDDhhmm at a
minute granularity. Process_Status is 'N' for a new file and 'F' for
that which has already been merged with its pair. FileID is the join
condition.

The query used by the application to pick up a pair of files is:

select a.FileID, a.File_Path, b.FileID, b.File_Path
from Job_Queue_1 a, Job_Queue_2 b
where a.FileID = b.FileID
and a.Process_Status = 'N' and b.Process_Status = 'N'
order by a.File_TimeStamp limit 1 ;

This runs very well for upto two million rows in each table. But I was
doing some stress testing with 4 million rows in each table, 2.5 with
Process_Status as 'F' and 1.5 with Process_Status as 'N'. The query was
hitting the database almost 50 times each second. I noticed that for 5
minutes the query would be very fast - about 20 milliseconds per query
and the explain statement on MySQL showed "Using where". And randomly
for 5 minutes the same query would drastically degrade in performance
and take about 30 seconds and the explain statement would show "Using
where, using temporary, using filesort". And then it would go back to
being fast.

Any clue of what might be happening here? The server is running on
RHEL3 with dual AMD CPUs and and the innodb_buffer_pool_size is 1.8 GB.

Thanks in advance.