Dos documentos:

Um objeto de operação pode estar no máximo em uma fila de operações por vez e esse método lança uma exceção NSInvalidArgumentException se a operação já estiver em outra fila. Da mesma forma, esse método lança uma exceção NSInvalidArgumentException se a operação estiver atualmente em execução ou já tiver terminado.

Então, como verifico se posso adicionar com segurança uma NSOperation a uma fila?

A única maneira que eu sei é adicionar a operação e tentar capturar a exceção se a operação já estiver em uma fila ou executada anteriormente.