More on 'who should she see': what part of speech is 'should' in this phrase?

Prompted by What does 'should' mean in this sentence?, instead of asking what it means, I'm interested in what part of speech it is.

The sentence is:

She walked through the forest, and who should she see, but the Big Bad Wolf

Should is being used to mean did in this sentence, which is an unusual use for should.

The general form seems to be:

[Interrogative] should [event] but [...]

(But is replaceable by except, only, etc.)

Is this a subjunctive? Is it a vestige from Old English?

Solution 1:

This seems to be OED sense 17 for "shall":

17. In questions introduced by who, whom, what, and followed by but, serving to express the unexpectedness of some past occurrence.

1626 Bp. J. Hall Contempl. VIII. O.T. xxi. 459 Whiles his hart is taken vp with these thoughts, who should come ruffling by him, but‥Haman.
1832 Tennyson May Queen iv, in Poems (new ed.) 91 As I came up the valley whom think ye should I see, But Robin?
1842 R. Browning Pied Piper iv, Just as he said this, what should hap At the chamber door but a gentle tap?
1945 R. Gibbings Lovely is Lee xxvii. 133 On the 23rd of March 1889 who should be born in Cork but myself?

Since the earliest citation is 1626, it does not seem to be a vestige from Old English.

The answer to "what is the part of speech?" is "modal".

Solution 2:

It is used here as an auxiliary verb.