Hello GAF! (First post ^^)
Cheap is an expression that intrigues me when used for a game, whatever the genre. It's a pretty subjective one, and I'm totally guilty of using it in the past, especially on fighting games; moreso against human opponents than AI...
One major example is CvSNK2, which I play with some uni buddies pretty frequently - I play as Kim a lot, and let out an almighty groan when I see our 'Hall Champion' pick Yamazaki. Over time, I've come to realise that his constant abuse of the serpent slash and ridiculous throwing priority are not necessarily 'cheap tactics', but just where I fail to meet his standard. Yamazaki is a veritable beast, and if I'm gonna be bouncin' off the walls the whole time then I deserve to get my ass slashed! I think the problem is that a person knows what they're doing when they use the same hideously effective move over and over again, whereas AI is just using patterns. Patterns which, as others have mentioned, can be read and countered.
I can understand the qualms people have with end bosses that use unfair 'rules' and such, but in gerenal, fast-paced action games such as NG shouldn't be labelled cheap on account of their (often insane) difficulty. Take the off-screen projectiles argument: is this to say that if you can't see an enemy, it shouldn't be able to harm you? Sounds kinda silly - if I were a real ninja (some day...) who could block bullets with his sword, and there was a guy with a gun a good few meters away, I'd bloody well be patient until I could let rip at close range!
Take away the ability to block, and yes, this pumelling of bullets might well fall into cheap territory. But hold up - there's no ability to block in something like CS. Does this mean getting shot while reloading is cheap? Probably not, it's just a part of gaming life. As someone stated before, there should always be at least one way to get round a seemingly unstoppable attack, or break a deadly pattern. If there is nothing that can ever be done, then by all means, it's Cheap.