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;


mmysql> 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\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: lb_partner
         type: ref
possible_keys: PRIMARY,partner_category,partner_language
          key: partner_category
      key_len: 4
          ref: const
         rows: 5998
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: lb_link
         type: eq_ref
possible_keys: link_partner_id,link_site_id
          key: link_partner_id
      key_len: 8
          ref: link_builder.lb_partner.partner_id,const
         rows: 1
        Extra: Using where
2 rows in set (7.50 sec)

ERROR: 
No query specified