One can encode this problem as a maximum-cost propositional SAT problem.
Let there be a propositional variable $x_v$ for each vertex $v$ in the graph. There are two types of constraints:
Covering constraints: for each edge $(u,v)$, one endpoint must be included. That is, $x_u \vee x_v$ must hold.
Minimality constraints: suppose vertex $v$ has neighbors $u_1,\ldots, u_k$; $v$ can be removed if and only if all its neighbors are included in the cover.
The constraint for $v$ is therefore $\neg x_v \vee \neg x_{u_1} \vee \cdots \vee \neg x_{u_k}$. (If vertex $v$ is isolated, its minimality constraint boils down to $\neg x_v$.)
If the graph has $n$ nodes and $e$ edges, the number of literals in the CNF formula is at most $n + 4e$. It is "at most," because some minimality constraints are subsumed by others. In the example above, the minimality constraints for $v_2$ and $v_4$ are subsumed by the constraints for $v_1$ and $v_5$, respectively. Once subsumed constraints are removed, the CNF formula cannot be further simplified.
One then looks for a satisfying assignment that has the greatest number of asserted variables.
We now show that the decision version of the problem (does this graph have a minimal vertex cover of size at least $k$?) is NP-complete. The proof is also going to work for size exactly equal to $k$.
The problem is in NP because a solution can be verified in polynomial time by checking that it has the required size and satisfies all constraints. As noted in the comments, this does not require translation to SAT.
We show that the problem is NP-hard by reducing CNF SAT to it. The strategy is adapted from M. D. Plummer, "Well-covered graphs: a survey", Quaestiones Mathematicae, 16(3):253–287, 1993.
Suppose we are given a propositional CNF formula $F$ that contains at least one clause, no empty clause, and no repeated clauses. Furthermore, no clause contains both a variable and its negation, or repeated literals. If any of these conditions are violated, either satisfiability is trivially decided (e.g., $F$ contains the empty clause) or $F$ can be easily simplified.
Let $F$ consists of $n$ clauses over $k$ variables. We create a graph $G$ as follows. There are $2k+n$ vertices: one vertex for each literal and one for each clause. Each literal is connected to its negation. Each clause is connected to all other clauses. (The clause vertices form a clique of size $n$.) Finally, every clause is connected to all its literals. This construction can be completed in polynomial time.
It is readily seen that an independent set of $G$ may contain at most one clause vertex and at most $k$ literal vertices. We can take this one step further: if $F$ is satisfiable, there are maximal independent sets of sizes $k$ and $k+1$, whereas if $F$ is unsatisfiable, all maximal independent sets have size $k+1$.
In fact, an assignment to the $k$ variables of $F$ identifies an independent subset of the literals of size $k$. If the assignment satisfies all clauses, no clause vertex can be added to this independent set, which is therefore maximal; otherwise, one of the unsatisfied clauses can be added to the set.
Regardless of whether $F$ is satisfiable, we can build a maximal independent set of size $k+1$ as follows: we pick one clause and an independent set of $k$ literals that are not in the clause. (That is, for every literal in the clause, we pick its negation, and for every variable not in the clause, we pick one of its literals.)
In sum, $F$ is satisfiable if and only if $G$ has maximal independent sets of size $k$. Said otherwise, $F$ is satisfiable if and only if $G$ has minimal vertex covers of size at least $k+n$.
Best Answer
Such a set $S$ is called a feedback vertex set, and the Wikipedia article mentions that it remains NP-hard even for very sparse directed graphs: even when each vertex has at most two edges going in, and at most two edges going out.
This makes it unlikely that there are nontrivial special cases that are easy. But it's known (Chen, Liu, Lu 2007) that the problem for all directed graphs is fixed-parameter tractable in the following sense: if you are given a fixed value $k$ and want to know if there's a feedback vertex set of size $\le k$, then there's an algorithm that's polynomial in $n$, the number of vertices in the graph. (But with a horrible dependency on $k$.)