MySQL issue with select query and 'order by' clause

We're experiencing a strange problem with a SELECT query against a MySQL database (InnoDB).

The following query incorrectly returns 1 matching record:

select `ID` 
from `AccessTables` 
where `numTableID` = 14 
    AND `numUserCatID` IN (7,253) 
    AND (`numUpdateCat` = 2 OR `numUpdateItems` = 2) 
order by `ID` asc 
limit 1

whereas the following query correctly returns no matching records:

select `ID` 
from `AccessTables` 
where `numTableID` = 14 
    AND `numUserCatID` IN (7,253) 
    AND (`numUpdateCat` = 2 OR `numUpdateItems` = 2) 
limit 1

As you can see, the only difference between these queries is the 'order by' clause.

The ID column requested in the query is the autogenerated primary key column for the table.

The record returned in the 1st query is a record that would be found if there were no brackets around the 'or' clause. But there ARE brackets around that part of the query, so I don't understand why this record is returned here. And then only if there is an 'order by' clause in the query.

The MySQL version in use is: MySQL Server: 5.5.32-MariaDB-log

Can anyone here shed some light on this issue? Thanks in advance.

(EDIT: leaving out the brackets does return a row, but that's another row than the one returned by the 1st query)

 insert  into `AccessTables`(`ID`,`numUserCatID`,`numTableID`,`numUpdateCat`,`numPublishCat`,`numUpdateItems`,`dateInsert`,`dateUpdate`,`numInsertAuthorID`,`numUpdateAuthorID`,`numViewItems`) values (71,15,14,0,0,2,'2008-03-13 23:38:47','2013-04-04 09:34:36',0,513,2);

(EDIT nr. 2: no MariaDB, but .... http://sqlfiddle.com/#!2/2a922/8)

Edit nr. 3, running these queries against the real MariaDB thing:

Query1:

EXPLAIN EXTENDED SELECT `ID` 
FROM `AccessTables` 
WHERE `numTableID` = 14 
    AND `numUserCatID` IN (7,253) 
    AND (`numUpdateCat` = 2 OR `numUpdateItems` = 2) 
ORDER BY `ID` ASC 
LIMIT 1;

Output:

"id"    "select_type"   "table" "type"  "possible_keys" "key"   "key_len"   "ref"   "rows"  "filtered"  "Extra"<br />
"1" "SIMPLE"    "AccessTables"  "range" "numUserCatID,numTableID,numUpdateCat,numUpdateItems"   "numTableID"    "8" \N  "136"   "11.03" "Using where"

Query2:

EXPLAIN EXTENDED SELECT `ID` 
FROM `AccessTables` 
WHERE `numTableID` = 14 
    AND `numUserCatID` IN (7,253) 
    AND (`numUpdateCat` = 2 OR `numUpdateItems` = 2) 
LIMIT 1;

Output:

"id"    "select_type"   "table" "type"  "possible_keys" "key"   "key_len"   "ref"   "rows"  "filtered"  "Extra"<br />
"1" "SIMPLE"    "AccessTables"  "range" "numUserCatID,numTableID,numUpdateCat,numUpdateItems"   "numUserCatID"  "8" \N  "20"    "75.00" "Using index condition; Using where"

Query3:

EXPLAIN EXTENDED SELECT `ID` 
FROM `AccessTables` 
WHERE `numTableID` = 14 
    AND (numUserCatID = 7 OR numUserCatID = 253) 
    AND (`numUpdateCat` = 2 OR `numUpdateItems` = 2) 
ORDER BY `ID` ASC 
LIMIT 1;

Output:

"id"    "select_type"   "table" "type"  "possible_keys" "key"   "key_len"   "ref"   "rows"  "filtered"  "Extra"<br />
"1" "SIMPLE"    "AccessTables"  "range" "numUserCatID,numTableID,numUpdateCat,numUpdateItems"   "numTableID"    "8" \N  "136"   "11.03" "Using where"

EDIT nr. 4: Removing the 'limit 1' has the same result as removing the 'order by': no rows are found.

Query 4:

EXPLAIN EXTENDED SELECT `ID` 
FROM `AccessTables` 
WHERE `numTableID` = 14 
    AND `numUserCatID` IN (7,253) 
    AND (`numUpdateCat` = 2 OR `numUpdateItems` = 2) 
ORDER BY `ID` ASC;

Output:

"id"    "select_type"   "table" "type"  "possible_keys" "key"   "key_len"   "ref"   "rows"  "filtered"  "Extra"<br />
"1" "SIMPLE"    "AccessTables"  "range" "numUserCatID,numTableID,numUpdateCat,numUpdateItems"   "numUserCatID"  "8" \N  "20"    "75.00" "Using index condition; Using where; Using filesort"

So, the queries that return the correct result (0 records found) seem to work with the index on numUserCatID, whereas the queries that return the incorrect result (1 record found) seem to work with the index on numTableID.

Strange...!

EDIT nr. 5:
Ordering by another column, eg. dateInsert (which is a date/timestamp representing the moment the record was inserted into the table), also changes the query result.
Then there are again no records returned and the index used is the one on numUserCatID again.

We were using the 'order by ID asc' because we assumed that the ID's would always represent the order in which the records were inserted into the DB.
But dateInsert does essentially the same in our case.

Would there be performance penalties in a large database when using a regular key column for ordering instead of the primary key?