Can "may/willshall have done" be used in the past?

I know that I could use "could/might/would/should have done" in the past tense, like:

He knew that she couldn't have stolen it.

He knew that she might not have stolen it. 

He knew that she wouldn't have stolen it. 

He knew that she shouldn't have stolen it. (All the four sentences refer to "past probability")

But I wonder if we can really use "may/will/shall have done" in the past tense? Like:

He knew that she may not have stolen it. (It means "He knew that she probably hadn't stolen it.")

He knew that she will not have stolen it. (It means "He knew that it was very likely that she hadn't stolen it.")

He knew that she shall not have stolen it. (Same as the above)

May I ask if all the three sentences are all suitable? Please give me your opinion, thank you.

 ---
Will have + past participle can express certainty or confidence about the past:

Dear Sir, You will recently have received a form ...

We can't go and see them now--they'll have gone to bed.

Swan, Practical English Usage, (will)
--

 The shall have isn't used today in AmE except in legal contexts with a mandating/deontic/obligation meaning. 

The enclosed is historical/old usage, with the meaning of obligation imposed by resolve: "it is our  moral obligation to ensure that they haven't died in vain": 

--
"It is rather for us to be here dedicated to the great task remaining
before us - that from these honored dead we take increased devotion to
that cause for which they gave the last full measure of devotion -
that we here highly resolve that these dead shall not have died in
vain - that this nation, under God, shall have a new birth of freedom,
and that government of the people, by the people, for the people,
shall not perish from the earth."

On 19 November 1863 President Abraham Lincoln dedicated a cemetery on
a Civil War battlefield
[url]http://news.bbc.co.uk/1/hi/world/americas/2250665.stm/url]

-----

Viceidol

All the four sentences refer to "past probability"

It's difficult to understand exactly what you mean by this comment.  And even after deciphering it to some extent, it doesn't seem true.  Far from relating to past probability, couldn't have stolen it, for example, is about an impossibility, at least in the most typical reading.  By modulating the voice so as to separate could from not (but never with the contracted form couldn't), you might indicate past probability, but I'd say that that is a secondary reading of that verb group -- a reading that is particularly difficult after He knew, which indicates a great deal of certainty, with which the probability reading clashes.

Secondly, none of the second group of examples is good because of the problems with the sequence of tenses.  After He knew (a past), only modals that are past in form (could, should, would, might, and possibly must) should be used.

CJ