Learning with "taciturn" oracles My question is a bit generic, so I'm making up a nice story to justify it. Bear with me if it's not realistic ;-)

Story

Mr. X, the head of the computer security department at a big company, is a bit paranoid: he requires that all employees change their passwords once a month, in order to minimise the risks of identity or information theft. Moreover, he does not trust the employees to be able to come up with secure passwords. 

Therefore, every month, he generates new passwords using a piece of software he wrote, and gives them to the employees so that they can log in again. But besides being paranoid, Mr. X is also a bit lazy: the passwords he generates all follow some pattern, and the algorithm used to allow people to log in only checks that the password "looks okay" according to that rule, and that it is not in the "expired list".

Unfortunately, his pretentious behaviour made a lot of people bitter, and one of them, Mr. Y, decides to prove him that he can crack his passwords. So, one night, he collects a few of them, and starts trying to design a learning algorithm for generating valid passwords, using his personal computer to verify them.

Question

The oracle used by Mr. Y is a bit strange, in that it tells him "the truth, but not the whole truth" (hence the "taciturn" adjective). More precisely: Mr. Y will know that a password is valid when his computer accepts it, but when a password is rejected, Mr. Y will not know whether or not it could have been valid: the password may be rejected because it does not correspond to some pattern, but it may also be rejected because it used to be valid but no longer is, according to Mr. X's "change once a month"-rule.

So, will Mr. Y ever be able to come up with anything in that setting? Or can we claim/prove that Mr. X's passwords are inherently unpredictable (as defined in the PAC learning setting, but maybe this concept exists in other frameworks)?
It seems you're trying to PAC learn a language by only seeing positive examples.  This is called "learning from positive examples (only)."  But you also have the power to get some of your own made-up examples labeled: if the oracle were fully truthful, then these would be membership queries, so your model would be known as "learning from positive examples and membership queries."  In this framework, there are some results - for example, tree languages are learnable (not secure).  DFA are not due to crypto hardness results. (Also see this.)

Of course, your setting isn't quite this.  Your membership queries are more limited.  It seems that then the known intractability results would transfer to your setting from the model I described, but the learnability results would leave you with some work to do.  But Mr. X's scheme is secure or not depending on the "pattern" he uses.

Also - it seems like a strange requirement to be able to prove "Mr. X's passwords are inherently unpredictable."  Isn't it usually enough to just be able to generate a new valid password to break such a system? But this seems to be the query to Mr. Y's algorithm itself...