Same problem here (and yes, every request is authorized). I am using the 1.1 endpoint (statuses/mentions_timeline), supply with count=200 and similar details. Call returns zero results. I run it again, zero results. I run it again, all results there.
I ran this over a batch of users, and about every 7th or 8th user got successful results back on the first attempt.
@episod Similar to other issues, is the count size too large and the request times out on your side maybe?