I'm taking a guess, but I think it came about during the 60's/70's. Before that economies usually had full employment (eg. Australia's unemployment rate rarely went above 2%). But it was around this time that the baby boomers began entering the workforce and the dramatic increase in the size of the labour force caused unemployment to reach such a size that marcoeconomic policy alone could not effectively reduce unemployment enough. So my guess is that the NAIRU was developed at this point as an excuse by governments and as long as there is unemployment politicians will use it as their magic bullet!
Phillips curve is right (ie. short term relationship between unemployment and inflation). Natural rate is wrong, IMO it's just cyclical unemployment that can be eliminated with enough aggregate demand (you just need lots of it).