This is a very small MIP:
Starting Gurobi... Optimize a model with 24 rows, 54 columns and 132 nonzeros Presolve removed 6 rows and 6 columns Presolve time: 0.11s Presolved: 18 rows, 48 columns, 114 nonzeros Variable types: 12 continuous, 36 integer (0 binary)

so I expected to run this very quickly on a fast 8 core Xeon machine. The time limit of 9999 seconds should be no problem even with the OPTCR (rel. gap tolerance) of 0.0. But I see:
835689342 7572026 infeasible 63 0.00062 0.00000 100% 1.0 9980s 836077602 7576642 0.00000 65 14 0.00062 0.00000 100% 1.0 9985s 836454289 7582365 0.00000 56 15 0.00062 0.00000 100% 1.0 9990s 836850333 7587882 0.00000 45 15 0.00062 0.00000 100% 1.0 9995s Cutting planes: Gomory: 1 MIR: 2 Explored 837155963 nodes (841647794 simplex iterations) in 9999.00 seconds Thread count was 8 (of 8 available processors) Time limit reached Best objective 6.179540598832e04, best bound 0.000000000000e+00, gap 100.0000% MIP status(9): Optimization terminated due to time limit.

This is not a Gurobi problem: Cplex is just as bad. Apparently these branch and bound methods are just not suited very well for this problem. I have solved some huge problems with hundreds of thousands of binary variables, but here we see some evidence, not all problems are that easy.
Recently I saw someone writing:
gurobi> m.setParam('Threads',80)
You may all drool now.
Guess we need something like that to solve my tiny 36 integer variable problem….
Notes:
 The OPTCR (gap tolerance) setting is not an issue as it turns out the best bound remains at 0.0, so a gap of 100% is reported.
 Gurobi is solving the nodes pretty efficiently. Approx. 1 simplex iteration per node, and > 80k nodes per second.
Update
Some Cplex runs solve this fast (see comments below), but on some machines I see the same problem:
Cplex 12.3.0.0 Reading data... Starting Cplex... Tried aggregator 2 times. MIP Presolve eliminated 1 rows and 1 columns. MIP Presolve modified 36 coefficients. Aggregator did 6 substitutions. Reduced MIP has 18 rows, 48 columns, and 114 nonzeros. Reduced MIP has 0 binaries, 36 generals, 0 SOSs, and 0 indicators. … Elapsed real time = 9880.28 sec. (tree size = 1251.36 MB, solutions = 70) Nodefile size = 1123.85 MB (527.18 MB after compression) 478309344 6481362 0.0000 15 0.0012 0.0000 5.26e+008 100.00% 479049990 6483695 0.0000 15 0.0012 0.0000 5.27e+008 100.00% 479749224 6499596 0.0000 15 0.0012 0.0000 5.27e+008 100.00% 480524806 6502892 infeasible 0.0012 0.0000 5.28e+008 100.00% 481284148 6500253 0.0000 16 0.0012 0.0000 5.29e+008 100.00% 482022525 6501343 0.0000 16 0.0012 0.0000 5.30e+008 100.00% 482764367 6511470 0.0000 16 0.0012 0.0000 5.31e+008 100.00% Mixed integer rounding cuts applied: 2 Zerohalf cuts applied: 2 Gomory fractional cuts applied: 2 Root node processing (before b&c): Real time = 0.03 Parallel b&c, 4 threads: Real time = 9998.98 Sync time (average) = 420.45 Wait time (average) = 45.69  Total (root+branch&cut) = 9999.01 sec. MIP status(107): time limit exceeded Fixing integer variables, and solving final LP... Parallel mode: deterministic, using up to 2 threads for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 25 rows and 55 columns. All rows and columns eliminated. Fixed MIP status(1): optimal Resource limit exceeded. MIP Solution: 0.001230 (530937464 iterations, 482992718 nodes) Final Solve: 0.001230 (0 iterations) Best possible: 0.000000 Absolute gap: 0.001230 Relative gap: 1.000000

This is a worse solution than Gurobi found. But on a different machine using 8 threads:
Cplex 12.3.0.0 Reading data... Starting Cplex... Tried aggregator 2 times. MIP Presolve eliminated 1 rows and 1 columns. MIP Presolve modified 36 coefficients. Aggregator did 6 substitutions. Reduced MIP has 18 rows, 48 columns, and 114 nonzeros. Reduced MIP has 0 binaries, 36 generals, 0 SOSs, and 0 indicators. … 129959 4046 0.0003 10 0.0031 0.0003 113627 91.54% *165794 5594 integral 0 0.0027 0.0005 146606 81.09% *170030 4859 integral 0 0.0019 0.0005 149634 72.63% *193953 3702 integral 0 0.0007 0.0006 171409 15.85% *195840 418 integral 0 0.0006 0.0006 172394 2.03% Mixed integer rounding cuts applied: 3 Gomory fractional cuts applied: 1 Root node processing (before b&c): Real time = 0.12 Parallel b&c, 8 threads: Real time = 4.10 Sync time (average) = 0.39 Wait time (average) = 0.02  Total (root+branch&cut) = 4.23 sec. MIP status(101): integer optimal solution Fixing integer variables, and solving final LP... Parallel mode: deterministic, using up to 2 threads for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 25 rows and 55 columns. All rows and columns eliminated. Fixed MIP status(1): optimal Proven optimal solution. MIP Solution: 0.000616 (175023 iterations, 203294 nodes) Final Solve: 0.000616 (0 iterations) Best possible: 0.000616 Absolute gap: 0.000000 Relative gap: 0.000000

So we have some very different behavior here: optimal in just 4 seconds.