The affected consumer key is YjwgRG5zOswde0yNg6YQmA
“If at all possible, could you capture one of these somewhat deterministic 401s (just after having the access token yielded) and post the HTTP headers you got in the response?”
Incidently, since my token is working today, (and I have no logs of the previous headers) it’s going to be a hard task. I revoked access to the app and retrieved a new token for my test account and the token worked as expected (I can for example retrieve results from /users/lookup.json). I also tried to authorize another account and it seemed to work… Is the lag gone ?
However, calling /account/verify_crendtials.json yields a 404, so there is still something not quite right :
# - {"x-frame-options"=>["SAMEORIGIN"], "x-ratelimit-reset"=>["1350567549"], "x-ratelimit-limit"=>["150"], "x-transaction"=>["10b68254fdb01739"], "last-modified"=>["Thu, 18 Oct 2012 13:26:35 GMT"], "expires"=>["Tue, 31 Mar 1981 05:00:00 GMT"], "content-type"=>["application/json; charset=utf-8"], "date"=>["Thu, 18 Oct 2012 13:26:35 GMT"], "x-runtime"=>["0.02374"], "server"=>["tfe"], "x-ratelimit-class"=>["api"], "x-ratelimit-remaining"=>["141"], "content-length"=>["68"], "x-mid"=>["f14e974fce970d05187931c114ee789744926efb"], "set-cookie"=>["k=10.36.23.106.1350566795744204; path=/; expires=Thu, 25-Oct-12 13:26:35 GMT; domain=.twitter.com", "guest_id=v1%3A13505667957462978; domain=.twitter.com; path=/; expires=Sun, 19-Oct-2014 01:26:35 GMT", "dnt=; domain=.twitter.com; path=/; expires=Thu, 01-Jan-1970 00:00:00 GMT", "lang=en; path=/", "lang=en; path=/", "_twitter_sess=BAh7CDoPY3JlYXRlZF9hdGwrCO%252FZDXQ6ASIKZmxhc2hJQzonQWN0aW9uQ29u%250AdHJvbGxlcjo6Rmxhc2g6OkZsYXNoSGFzaHsABjoKQHVzZWR7ADoHaWQiJTc3%250AMWU3NmMwNzNkOWZlNjE0ZWM3ZmRlZmZhMzU0OTEw--3902082c62c8301e10b93eff91d48d1511fc55a9; domain=.twitter.com; path=/; HttpOnly"], "status"=>["404 Not Found"], "cache-control"=>["no-cache, no-store, must-revalidate, pre-check=0, post-check=0"], "vary"=>["Accept-Encoding"], "pragma"=>["no-cache"]}
Yesterday, I’m pretty sure it was 401 all the way (both verify_credentials and other endpoints).
“Does the same access token that’s having trouble just after issuing eventually become functional?”
I can’t guarantee this 100% but I just tried on the token I tested yesterday just before posting and sure enough it seems to be working now ?! This seems to concur with your idea. However, is there a way to go back to a near real-time delay ? 
Wilfried