What Ive noticed, rejects occur mainly on gpus that is busy with a long hash ie. longpoll doesnt seem to correctly allways drop the old work that the gpu might be busy with.
Would the queue depth? Running cgminer with a queue of 2 it seems like it keeps working on the old work for quite awhile. This is my office desktop that's just running a single 6870 at about 300MH/s. It seems to be an excessive amount of rejects in one go, but it only happens infrequently. This would have happened at 19:00 UTC.
[2012-04-19 13:00:56] Accepted 00000000.cfcd80e0.104c0a23 GPU 0 thread 0 pool 0
[2012-04-19 13:01:05] LONGPOLL detected new block on network, waiting on fresh work
[2012-04-19 13:01:08] Rejected 00000000.45665b79.c108b63d GPU 0 thread 0 pool 0
[2012-04-19 13:01:24] Rejected 00000000.9ecfb9ed.6fa7198c GPU 0 thread 1 pool 0
[2012-04-19 13:01:51] Rejected 00000000.90610cd4.47e441ba GPU 0 thread 0 pool 0
[2012-04-19 13:01:52] Rejected 00000000.480ad701.1d873186 GPU 0 thread 0 pool 0
[2012-04-19 13:02:11] LONGPOLL detected new block on network, waiting on fresh work
[2012-04-19 13:02:12] Rejected 00000000.96d36cb2.e8aeea3a GPU 0 thread 0 pool 0
[2012-04-19 13:02:16] Rejected 00000000.057d0d22.74acf4a4 GPU 0 thread 1 pool 2
[2012-04-19 13:02:29] Rejected 00000000.d9de5e22.7769897f GPU 0 thread 0 pool 0
[2012-04-19 13:02:30] Rejected 00000000.d26cf9a7.866b3b22 GPU 0 thread 1 pool 2
[2012-04-19 13:02:31] Rejected 00000000.de395ccc.71ea79ec GPU 0 thread 0 pool 0
[2012-04-19 13:02:32] Rejected 00000000.b388c75a.6c83d933 GPU 0 thread 1 pool 2
[2012-04-19 13:02:52] Rejected 00000000.b82844cc.402565aa GPU 0 thread 0 pool 0
[2012-04-19 13:03:30] Accepted 00000000.5bd40d89.ad756376 GPU 0 thread 1 pool 0
[2012-04-19 13:03:33] Accepted 00000000.35d270d2.0a190f78 GPU 0 thread 1 pool 0
[2012-04-19 13:03:38] Accepted 00000000.122a4e56.0abf1b39 GPU 0 thread 0 pool 0