Constructions using have
in this manner are indeed common in old literature:
'I should have thought him a clergyman, but for his having no Reverend here,' said I.
Source: Dickens, Charles, Hunted Down
I beg your pardon, Mr. Dashwood, but if he had done otherwise, I should have thought him a rascal.
Source: Austen, Jane, Sense and Sensibility
If I did not know that the play was Shakespeare's, I should have thought it must have been one of those early tragedies of blood and horror from which he is said to have redeemed the stage'?
Source: Bradley, A. C. Shakespearean Tragedy: Lectures on Hamlet, Othello, King Lear, Macbeth. 2nd ed. London: Macmillan, 1905.
You are absolutely correct when you suggest substituting should
with would
- this is a very idiomatic expression and these should
s should not be read nor taken literally. These uses of should have thought
are perfectly equivalent to the use of would have thought
in this line:
Yet who would have thought the old man to have had so much blood in him?
Source: Shakespeare, William, Macbeth V.i.39-40
In American English, at least - as jimsug has noted - this is language particular to period literature and the discussion thereof, and would never be encountered in daily conversation used in this fashion. Perhaps it may be a more natural expression in some other region (for instance, in London it is apparently fairly common to say "mind the gap" when people are boarding trains, as a way of warning them to be mindful of the gap between the train station platform and the train itself, but in the States using "mind" as a verb is already fairly uncommon, and even more so in this fashion).
The second example uses "should have" in a more modern construction, although the use of "fitted" here is rather dated. I would suggest reading it as
It was clearly not the job for which his age and education should have prepared him.
That being said, should have
is not in itself a wholly antiquated phrase to use, but in modern usage is taken much more literally, and is much more common as a contraction:
You really should've studied for that test instead of staying out all night.
Yeah, I should've thought of that, but it's too late for that now.
Did you at least talk to the professor immediately, like you should've?
One might also use should have
in place of should've
for a more pronounced effect, as is the case for most contractions (as the Google results for "should have thought" will show).
It's worth noting that in contexts where people are not paying attention to grammar and/or spelling, it's not uncommon to see should of
where should've
is the correct phrase to use, because they are pronounced in more or less exactly the same manner.