mysql> SHOW CREATE TABLE lb_link\G;
*************************** 1. row ***************************
       Table: lb_link
Create Table: CREATE TABLE `lb_link` (
  `link_id` int(10) NOT NULL auto_increment,
  `link_partner_id` int(10) NOT NULL default '0',
  `link_site_id` int(10) NOT NULL default '0',
  `link_linkback_url` varchar(255) character set utf8 NOT NULL default '',
  `link_status` int(5) NOT NULL default '0',
  `link_created_on` datetime NOT NULL default '0000-00-00 00:00:00',
  `link_modified_on` datetime NOT NULL default '0000-00-00 00:00:00',
  `link_created_by` int(10) NOT NULL default '0',
  `link_modified_by` int(10) NOT NULL default '0',
  PRIMARY KEY  (`link_id`),
  UNIQUE KEY `link_partner_id` (`link_partner_id`,`link_site_id`),
  KEY `link_linkback_url` (`link_linkback_url`),
  KEY `link_site_id` (`link_site_id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1
1 row in set (0.00 sec)


mysql> SHOW CREATE TABLE lb_partner\G;
*************************** 1. row ***************************
       Table: lb_partner
Create Table: CREATE TABLE `lb_partner` (
  `partner_id` int(10) NOT NULL auto_increment,
  `partner_category` int(4) NOT NULL default '0',
  `partner_language` varchar(2) character set utf8 NOT NULL default 'en',
  `partner_name` varchar(128) character set utf8 NOT NULL default 'link',
  `partner_description` text character set utf8,
  `partner_url` text character set utf8 NOT NULL,
  `partner_email` text character set utf8,
  `partner_form` varchar(255) character set utf8 NOT NULL default '',
  `partner_old_id` int(10) default NULL,
  `partner_created_on` datetime NOT NULL default '0000-00-00 00:00:00',
  `partner_modified_on` datetime NOT NULL default '0000-00-00 00:00:00',
  `partner_created_by` int(10) NOT NULL default '0',
  `partner_modified_by` int(10) NOT NULL default '0',
  PRIMARY KEY  (`partner_id`),
  KEY `partner_category` (`partner_category`),
  KEY `partner_form` (`partner_form`),
  KEY `partner_language` (`partner_language`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci
1 row in set (0.00 sec)

The slow queries:
Ordering by link_id takes 4x the time and it has 12,000,000 rows

# Time: 080408 17:46:46
# User@Host: link_builder[link_builder] @ localhost []
# Query_time: 24  Lock_time: 0  Rows_sent: 0  Rows_examined: 4675
SELECT  partner_name, partner_url, partner_description FROM lb_link LEFT JOIN lb_partner ON link_partner_id = partner_id WHERE link_site_id = 576 AND partner_category = '3' AND partner_language = 'jp' AND link_status IN (1,2)   LIMIT 1120, 40;
# Time: 080408 17:47:45
# User@Host: link_builder[link_builder] @ localhost []
# Query_time: 20  Lock_time: 0  Rows_sent: 40  Rows_examined: 10079
SELECT  partner_name, partner_url, partner_description FROM lb_link LEFT JOIN lb_partner ON link_partner_id = partner_id WHERE link_site_id = 130 AND partner_category = '2' AND partner_language = 'jp' AND link_status IN (1,2)   LIMIT 4400, 40;


mysql> explain SELECT  partner_name, partner_url, partner_description FROM lb_link LEFT JOIN lb_partner ON link_partner_id = partner_id WHERE link_site_id = 425 AND partner_category = '2' AND partner_language = 'jp' AND link_status IN (1,2)   LIMIT 1640, 40;
+----+-------------+------------+--------+-------------------------------------------+------------------+---------+------------------------------------------+------+-------------+
| id | select_type | table      | type   | possible_keys                             | key              | key_len | ref                                      | rows | Extra       |
+----+-------------+------------+--------+-------------------------------------------+------------------+---------+------------------------------------------+------+-------------+
|  1 | SIMPLE      | lb_partner | ref    | PRIMARY,partner_category,partner_language | partner_category | 4       | const                                    | 5998 | Using where | 
|  1 | SIMPLE      | lb_link    | eq_ref | link_partner_id,link_site_id              | link_partner_id  | 8       | link_builder.lb_partner.partner_id,const |    1 | Using where | 
+----+-------------+------------+--------+-------------------------------------------+------------------+---------+------------------------------------------+------+-------------+
2 rows in set (2.00 sec)