It is now almost two months since United last scored at home in the Premiership – Laurent Robert's free-kick winner over Liverpool. And it must be debatable whether they will score at St James' Park again this season with just champions-elect Chelsea to come.
A second successive home goalless draw in four days was not what the home fans to see and Souness did not attend the post-match press conference, choosing instead to send his deputy Alan Murray.
Alan Shearer made his 500th senior start and Shay Given chalked up his 250th Premiership appearance for United.
Newcastle's players have been told they must report back for pre-season training on June 22 - such is the legacy of having to play in the Intertoto Cup.
Shearer almost ended his scoring drought in the third minute when the fit-again Amdy Faye spread the ball wide to Stephen Carr whose near-post cross was whipped goalwards by the United skipper who was denied by an excellent Gabor Kiraly block.
A swift move after 11 minutes saw James Milner break free on the left and again Shearer got on the end of the cross, but it was easy save for Kiraly who could then only watch seconds later when Shola Ameobi lifted a Charles N'Zogbia well wide.
United started the second half with a flourish and Milner cutting in from the left brought a good save out of Kiraly.
Palace's best chances always looked like coming from set pieces and both Tony Popovic and Gonzalo Sorondo tested Given with headers.
Kiraly was caught out flapping at a 50th minute corner and when the ball was finally worked out to Darren Ambrose lurking on the edge of the area his shot flashed agonisingly wide.
There was a scare on the hour mark for Palace when Jean Alain Boumsong saw a downward header from an N'Zogbia cross go close.
United made a double switch after 69 minutes with Ambrose and Ameobi making way for Patrick Kluivert and Robert.
Both Steven Taylor and Kluivert had goals disallowed, though it looked very much that the Dutchman was not offside and assistant referee Jim Devine made a glaring mistake.
Man of the Match: Tony Popovic - The Aussie centre-half was dominant at the heart of the Palace defence to ensure his side held on for a point that could prove crucial to his side's hopes of avoiding relegation.