Solution:

Faride Firoozbakht found the following results:

f(x), f(m) is composite for all m up to

x^6 + 801967256, 28958
x^6 + 907906544, 33914
x^6 + 995925839, 29399
x^6 + 1209089636, 28118
x^6 + 1225641416, 34964

Later she added:

The largest value of k that I found for c < 0 is 39458; and for c > 0 is 36350, the corresponding polynomials are in the following table.

f(x) |f(m)| is composite for all m up to

x^6 - 2335031854 39458
x^6 + 2946524426 36350

***

The 31 of July (2004) Adam Stinchcombe wrote:

One approach proved very fruitful.  Starting with the idea that c0=5983049981 was a good value for c, i.e., it gave useful arithmetic properties mod various primes, namely one can solve x^6+c0=0 mod p for each p<=29, thus x^6+c0 will be large in size and divisible by small primes, and so therefore composite, for most values of x.  I then used a modulus of m=29#=6469693230, calculated ci=c0+m*i and came up with c=32386797666131, # of composites = 30323 and then c=432129733268141, # of composites = 53255

***

Phil Carmody got a new record for this puzzle and at the same time four larger examples than the gotten by Stinchcombe:

It looked like 30000 was easy to achieve, but the 40000s were pretty rare, and 50000s were absolutely impossible.

Here are the ones I found over 39458:

1292597109886991 46956
2683424369451671 39900
5436756742672646 40845
11117808561725774 45297
17577986970290501 40404
20726454730694621 41160
24164653747817519 42588
29450922301244534 63693
28715053738503404 51597
30059408353405976 45885
34964348452640606 53865
38631587821244354 56343
45223406878461356 53529

As you see, 50000 was impossible, until the 60000 removed whatever blockage was in my program :-). Note that large c makes it easier, so really there should be some weighting (maybe divide by log(c)) to make up for this.

***

On October 31, 2016, Dmitry Kamenetsky wrote:

x^12+488669 is composite for 0<x<616980, see http://oeis.org/A122131.

***