Controllo e restituzione di valori dal database

La tua condizione potrebbe essere semplificata, prova in questo modo:

if(isset($ref)){ 
    $db = mysql_connect('localhost', 'admin', "admin") or die(mysql_error("Cannot Connect to Database")); 
    mysql_select_db('tracking') or die(mysql_error());

    $sql = "SELECT * FROM order_tracking WHERE ship_ref = '".$ref."' "; 
    $rs  = mysql_query($sql);
    if(!rs){
        die(mysql_error());
    }

    if($row = mysql_fetch_array($rs)) {
        echo '<table width="518" border="1";>'; 

        echo '<tr>';
        echo '<td width="137" style="font-size:12px; padding: 5px;" >Shipment Reference: </td>';
        echo '<td width="365" style="background-color:#fcfcfc; padding: 10px;  font-size:12px;">' . $row['ship_ref'] . "<br />" . '</td>'; 
        echo '</tr>';

        echo '<tr>';
        echo '<td width="137" style="font-size:12px; padding: 5px;" >Shipment Type: </td>';
        echo '<td width="365" style="background-color:#fcfcfc; padding: 10px;  font-size:12px;">' . $row['ship_type'] . "<br />" . '</td>'; 
        echo '</tr>';
        echo "</table>";
    }
    mysql_close();
}
else{
    print 'Invalid Tracking Number, Please <a href="tracking.php"> click here </a> to try  again' ;
}

perché else if ($rs != $row) avrà un valore indefinito se la prima condizione non è soddisfatta.

Come ha sottolineato @marco, puoi controllare le righe senza recuperare:

if(mysql_num_rows($rs) > 0){
  //found a row
}