Comprobación y devolución de valores de la base de datos.

Su condición podría simplificarse, intente de esta manera:

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' ;
}

porque else if ($rs != $row) tendrá un valor indefinido si no se cumple la primera condición.

Como señaló @marco, puede buscar filas sin buscar:

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