Pretending the start symbol to not be nullable will lead to an $\varepsilon$-removal algorithm which is idempotent on all CFGs. I'll now formalize and prove this.
I define a non-terminal $A$ to be S-nullable iff
- It is not $S$ (the start symbol); and
- It either has a rule $A \to \varepsilon$ or it has a rule $A \to X_1 \ldots X_n$ where each $X_i$ is an S-nullable non-terminal.
The $\varepsilon$-removal algorithm then becomes:
Input: A context-free grammar $G = (N, \Sigma, S, P)$.
Output: A context-free grammar $G_\varepsilon$ with no S-nullable non-terminals and $L(G_\varepsilon) = L(G)$.
Procedure: let $G' = (N, \Sigma, S, P \setminus \{(A \to \varepsilon) \in P \mid A \not= S\})$. For each non-terminal $A$ in $N$ which is S-nullable in $G$, for each rule $B \to \alpha A \beta$ in $G'$, add the rule $B \to \alpha \beta$ to $G'$ if $\alpha \beta \not= \varepsilon$ or $B = S$ ($\alpha$ and $\beta$ are strings in $(N \cup \Sigma)^*$). Let $G_\varepsilon$ be $G'$ after all such rules have been added.
Note that one-by-one addition of rules means that if we have $S \to ABCd$ and $ABC$ is nullable and we nullify $A$, $B$, $C$ in that order, we will first add $S \to BCd$, then add $S \to ACd$ and $S \to Cd$, then add $S \to ABd \mid Bd \mid Ad \mid d$. In other words, it should be equivalent to doing the combinatorial expansion of rules one rule at a time.
Clearly $G_\varepsilon$ has no S-nullable rules: all $\varepsilon$ rules were removed (except $S \to \varepsilon$ if it was there), and no $\varepsilon$ rules were added (except maybe $S \to \varepsilon$). Hence no non-terminal is S-nullable directly (since $S$ is never S-nullable), and the inductive case has no basis to apply to.
Hence the algorithm is idempotent: it only adds or removes rules if there is an S-nullable non-terminal in $G$.
Also the algorithm preserves language, i.e. $L(G_\varepsilon) = L(G)$, by translation of derivations.
When we derive $A \Rightarrow \varepsilon$, we can instead avoid introducing $A$ in the first place, unless $A = S$ in which case $S \to \varepsilon$ is a rule. In the other direction, when we derive $\alpha \beta$ we can sprinkle it with (S-)nullable non-terminals and derive $\varepsilon$ from those.
Once more, with formality:
In one direction, when $\alpha \beta$ is derived from $A$ in $G_\varepsilon$ and $A \to \alpha \beta$ doesn't occur in $G$, this is because we added this rule based on finding $A \to \alpha B \beta$ with $B$ S-nullable. Either this rule occurs in $G$, in which case derive $\varepsilon$ from $B$, or this rule was itself added; let $\alpha' \beta' = \alpha B \beta$ such that we added $A \to \alpha' \beta'$ based on finding $A \to \alpha' C \beta'$ where $C$ is S-nullable.
Every inductive step searches for a right-hand side that's longer by 1 and bounded by the length of the longest rule in $G$, hence this process terminates. Derive $\varepsilon$ from all the back-filled non-terminals (they're all S-nullable). This will derive $\alpha \beta$ from $A$ in multiple steps, hence $\Rightarrow^*$ is preserved (in one direction).
In the other direction, if $\varepsilon$ is derived from $A$ (in a single step) where $A \to \varepsilon$ doesn't occur in $G_\varepsilon$, we know that $A \not= S$ (because we never remove $S \to \varepsilon$) and $A$ is S-nullable; hence we must have previously derived some sentential form containing $A$ in at least one derivation step.
Let $B \to \alpha A \beta$ be the rule which introduced the $A$ in question. If $\alpha \beta \not= \varepsilon$, we added the rule $B \to \alpha \beta$. Use this rule instead. (Any derivations performed between introducing and eliminating $A$ can still be performed, and have identical results.)
If $\alpha \beta = \varepsilon$, then either $B = S$ or $B$ is S-nullable. If $B = S$ we added the rule $S \to \varepsilon$; use this to replace the derivation $\gamma \underline{S} \delta \Rightarrow \gamma A \delta$ with $\gamma \underline{S} \delta \Rightarrow \gamma \delta$.
If $B \not= S$ it is S-nullable (as $B \Rightarrow A \Rightarrow \varepsilon$) and some other rule introduced $B$ to our sentential form. Apply the same replacement; the number of recursive steps is bounded above by the number of derivation steps done so far.
Unrelated observation: if in $G$ we have rules $S \to \varepsilon$ and $A \to \alpha S \beta$ then $G_\varepsilon$ will still have those rules, i.e. it will not be essentially non-contracting. However, if $S$ never occurs on the right-hand side of any rule in $G$, then $G_\varepsilon$ will be essentially non-contracting (and $S$ will also not occur on any right-hand side in $G_\varepsilon$).
