zajefajny
It's an euphemism for zajebisty, which is still considered rough by most people.
I remember Agnieszka Chylińska using it on TV, but I'm not sure when exactly and what programme it was. I don't think she was the first one either, but then I'm not much of a TV viewer.
And I remember "wypas" used by Gulczas, a guy from the 1st edition of the Polish Big Brother, in some sort of a TV commercial - something to do with cars probably, as the exact quote was "Nysa to jest wypas". I've just checked and the 1st edition of BB in Poland was in 2001, so the commercial must have been on the air soon after that - end of 2001? The expression was quite new then.