My Algorithm

Computing a new element of the Tribonacci sequence requires the last three elements.
They are called tri1, tri2 and tri3 in my code, the next element is triNext:
unsigned int triNext = tri1 + tri2 + tri3;

My divisibility check computes a number's modulo and aborts if it becomes zero (current is the current divisor, e.g. 27):
triNext %= current;
if (triNext == 0)
break;

Unfortunately, Tribonacci numbers get massive after just a few steps. Luckily:
(x + y) mod m = (x mod m + y mod m) mod m

Hence my variables tri1, tri2, tri3 and triNext don't have to store true Tribonacci numbers but only the remainder modulo the current divisor.

To find out for sure that a number is a non-divisor you have to find a cycle, that means that the remainders repeat themselves.
There are a few smart ways to do that in a 100% safe way - but I decided to have a fixed number of steps and assume a number is a non-divisor if it passed all tests.
The only optimization in my code is to detect whether tri1 == tri2 == tri3 == 1 because then it returned to the starting point and there is a loop.
(side note: that simple optimization is sufficient to reliably find the 124th number, though, and I'm not entirely sure why).
My prototype found that 1577 is the divisor where my program needed 22710 steps to prove that it divides a Tribonacci number.
That's why maxSteps = 22710.

Note

It seems divisor^2 is a hard limit for MaxSteps. My empirically found value is much smaller for most Tribonacci numbers and therefore faster.

The modulo operation triNext %= current; can be slow.
tri1, tri2 and tri3 are each smaller than current, therefore their sum triNext must be smaller than 3*current, too.
The following code is about twice as fast as the modulo operation (which I kept in my solution):
while (triNext >= current)
triNext -= current;

I thought that a fully unrolled loop could be even faster, but it isn't:
if (triNext >= current)
{
triNext -= current;
if (triNext >= current)
triNext -= current;
}