Bulls and cows possible as specified?

After struggling with my solution for some time, I finally managed to have it answer all of the test cases in 7 moves or fewer. Then, before publishing, I decided to test it exhaustively with all possible secret keys, to see if it would still be within the limit. It failed. I struggled considerably more and I still haven't found a solution that works all the time.

Then I took the four published solutions and tested them exhaustively. It seems that every one of them fails for some test case. E.g. cbrunet's failed for 2637, bunnychai's for 3458, and htamas's (who apparently was the only one who took this seriously) for 0913. Jcg's solution is randomized, so it will be harder for anybody to reproduce, but when I gave it a try it failed for 0175.

So, I'm wondering, is the limit feasible? Does the task author have a solution that works within the limit for all test cases?