Detecting if a CAPTCHA is needed
1, You should create those indexes. Explain shows whether your queries use indexes or not. If you don't have yet maybe you want a cron job which regularly deletes old records from the table. It improves performance too.

2, As others already mentioned on other questions, if possible, use PDO to avoid possible SQL injections.

3, Choose a meaningful names instead of $query1 and $query2 (maybe $remoteAddrQuery and $userIdQuery). It improves code readability a lot. The same is true for $result1 and $result2 ($remoteAddrResults, $userIdResults).

4, Maybe one query would be enough:

$attemptsQuery = "SELECT id FROM history 
    WHERE (Time &gt; date_sub(now(), interval 5 minute)) 
        AND (remote_addr='" . ip2long($_SERVER['REMOTE_ADDR']) . "' 
            OR userid='" . $userid . "')
    LIMIT 6"; 


5, If you don't use the queried records just the count of them use COUNT(*):

$attemptsQuery = "SELECT COUNT(*) as attempts FROM history 
    WHERE (Time &gt; date_sub(now(), interval 5 minute)) 
    ...
    LIMIT 6"; 


It results a little bit less network traffic between the webserver and the database server and maybe means lower database load.
Of course you have to change mysql_num_rows too.

6, Some comments is unnecessary:

//so we know mysql_num_rows($result2)


7, Instead of commenting create functions whose name say what the comments said. I'd change

$attempts=0; // we want to set up $attempts=maximum of 
             // (mysql_num_rows($result1), mysql_num_rows($result2))
if($result1) {
    $attempts=mysql_num_rows($result1);
}
if($result2 &amp;&amp; $attempts&lt;mysql_num_rows($result2)) {
    $attempts=mysql_num_rows($result2);
}


to

function getMaxAttempts($result1, $result2) {
    $attempts = 0;
    if ($result1) {
        $attempts = max($attempts, mysql_num_rows($result1));
    }
    if ($result2) {
        $attempts = max($attempts, mysql_num_rows($result2));
    }
    return $attempts;
}


It makes the code more readable.

Note that I've removed the first call of mysql_num_rows($result2) which maybe improves performance a little bit. (Probably PHP caches it.) A vararg function would be better with a loop but I don't know PHP supports it or nor.

8, If there is an error with the queries or with the database server mysql_query will return FALSE. Therefore, there will be no captcha displayed at all:

if ($result1) {
    $attempts = mysql_num_rows($result1);
}


Maybe you want to log and/or show an error message in these cases.