Not being aware that the Necromancer was Sauron is not the same thing as not believing that Sauron will ever return. The biggest surprise is that it actually took the Wise so long to put 2 and 2 together (or to even go and find out).
First of all, it was well known that the Ring was not destroyed. Elrond and Cirdan were both present when Isildur refused to destory it, and aside from that, the continued existence of the Nazgul (suspected in TA 1100, confirmed in TA 1300) is enough on it's own to confirm.
With the Ring not having been destroyed, and with Sauron's continued existence as a force for evil being dependent on the Ring, it naturally follows that it was well known that Sauron was still around and would return.
It then becomes a matter not of "if" but of "when". As is noted in Of the Rings of Power and the Third Age:
For Isildur would not surrender it to Elrond and Cirdan who stood by. They counselled him to cast it into the fire of Orodruin nigh at hand, in which it had been forged, so that it should perish, and the power of Sauron be for ever diminished, and he should remain only as a shadow of malice in the wilderness. But Isildur refused this counsel...
So even at the start of the Third Age, it would have been anticipated that Sauron would return.
Secondly, it's important to realise that there are two perspectives in this matter:
- The perspective of those in Middle-earth.
- The perspective of those in Valinor.
The Valar did indeed explicitly send the Istari for the purpose of contesting with Sauron, as we see from the Istari essay in Unfinished Tales (which was originally written for the abandoned index to Lord of the Rings):
Emissaries they were from Lords of the West, the Valar, who still took counsel for the governance of Middle-earth, and when the shadow of Sauron began first to stir again took this means of resisting him.
But while the Valar and the Istari too knew what their purpose was, those in Middle-earth did not (same source):
...for long they went about in simple guise, as it were of Men already old in years but hale in body, travellers and wanderers, gaining knowledge of Middle-earth and all that dwelt therein, but revealing to none their powers and purposes.
So while the non-destruction of the Ring and the possibility of Sauron's return were known to the Wise, these were matters that would have passed into legend so far as the common man (and common Man) in Middle-earth was concerned.
So in summary:
- Nobody was surprised that Sauron had returned,
- Yes, it was a foregone conclusion,
- Yes, the only question was how and where,
- Both Elrond and Cirdan knew that the Ring was not destroyed,
- That the Wise initially suspected that the power in Dol Guldur was a Nazgul confirms that they knew that the Nazgul were still around as early as TA 1100, therefore they also knew that the Ring wasn't destroyed,
- Sauron's non-demise at the end of the Second Age therefore wasn't surprising, it was known.
The only puzzling aspect in the whole matter is why did it take the Wise 1000 years before they decided to send somebody to check out Dol Guldur, and unfortunately that's something that as far as I know Tolkien never wrote an explanation for.