I don't think "out of nowhere" is a negative-polarity expression*. I think it is an idiom, which has had its negative polarity "bleached" out.
So its meaning "unexpected, surprising, intrusive" is constant whether the verb is negative or not:
Well, that came out of nowhere, didn't it!
It didn't come out of nowhere: there's been discussion on social media for days.
Out of somewhere and out of anywhere are perfectly grammatical, but do not partake of this meaning.
*It is possible to use it literally, rather than in the idiom, but I don't think it is common: You've copied that essay out a book, haven't you? No, I copied it out of nowhere!. In that use it would have negative polarity, so in standard English No, I didn't copy it out of anywhere!, but in non-standard versions No, I didn't copy it out of nowhere! (Compare standard I didn't touch anything! and non-standard so-called "double negation" I didn't touch nothing!)