How do I choose between ‘who’ or ‘whom’ when the subject pronoun is unclear?

The ‘simple’ substitution of he/him to determine whether to use who/whom does not always work for more complex sentences, sometimes leading to incorrect results, as a number of similar recent questions emphasise:

1. Conflicting who/whom usage rules in a sentence

2. The use of "whoever" or "whomever" in complex sentence

In the first example of such confusion the OP was not able to clarify the situation using the substitution rule and in the second, the OP had explained in comments that using the substitution rule led to a false 'whom' where 'who' is to be used. That shows the need for some sort of a simple algorithm that would help non-native speakers of English correctly choose who/whom for almost any situation, especially when the sentence has multiple subjects, objects, verbs and clauses.

I am still working on this very interesting topic but what I have managed to grasp is the following;

'who' is a subject pronoun and 'whom' is an object pronoun

as explained by Professor Malcolm Gibson's article Who is correct? Yes, though it may depend on whom you ask! which I referenced in two of my answers on ELU regarding who/whom: therefore an example of a practical approach that I would suggest at present would be

1. Look at the verb that requires who/whom:
   if the verb needs a subject pronoun, select ‘who’. If the verb does not need a subject pronoun, see whether it is a transitive or an intransitive verb.

2. If it is a transitive verb, it needs an object pronoun: so select ‘whom’

3. If it is an intransitive verb or a linking verb, it does not need an object pronoun: so select ‘who’.

4. In more complex sentences having multiple verbs, the choice of who/whom depends on whether the clause as a whole takes a subject pronoun or an object pronoun.

---

Appendix: Explanatory notes

The so-called ‘simple substitution rule’ given in earlier answers works especially well in simple sentences, as does my own method highlighted above. Problems arise when the sentence does not obviously require a subject pronoun, and the concerned verb is moreover not obviously transitive, making it difficult to decide whether it needs an object pronoun.

As @Peter Shor pointed out elsewhere in comments, problems also arise when the sentence has more than one verb, in which case the problem is how to decide which verb ‘who/whom’ would apply to: to determine which, some element of contextual reading and deconstruction might be required.

Example: “These are the men who they believe conspired to rob a bank.” – Peter Shor

Decoding this sentence, “what do they believe?” – “they believe (that) these men conspired to rob a bank.”

Whom is not to be used after ‘these are the men’ because the object of the transitive verb ‘believe’ is not ‘these men’ but the object clause, “these men conspired to rob a bank.”

Now it is notable that changing any verb other than 'believe' will not change the choice of who/whom: not even if a transitive verb like '(they) saw', which makes ‘these men’ its object, were to replace ‘conspired’; as in

they believe (that) they saw these men rob the bank:

these are the men who they believe they saw rob the bank.

Why not ‘whom’, since they saw these men? Aren't these the men whom they saw rob the bank? Not exactly, because they only 'believe' so – and the object of the verb ‘believe’ is again not ‘these men’ but the object clause 'they saw these men rob the bank' – in short, ‘these men’ never being the object of ‘believe’, ‘whom’ is not to be selected here.

Modifying the use of ‘believe’ a little will, however, change the choice of who/whom:

They believe these men to have conspired to rob the bank.

‘These men’ having finally become the object of ‘believe’, ‘whom’ is now required here.

These are the men (whom) they believe to have conspired to rob the bank.

Thus we might conclude, as @Andrew Leach suggested in a comment here, that

(4) in more complex sentences having multiple verbs, the choice of who/whom depends on whether the clause as a whole takes a subject pronoun or an object pronoun [paraphrase].

Expert members please evaluate this method and post comments suggesting corrections/improvements to the practical approach I have highlighted in this answer.

First of all, each of the examples given in the body of your question should be "whom."

This is a holdover from when the English language had cases, which you sort of referenced by noting the difficulty in identifying a subject. Who is always a subject, while whom is either a direct object, indirect object, or object of preposition:

1) Whom did you kill? (DO) 2) To whom did you give the book? (IO) 3) Who is the person about whom you are talking? (ObjP)

If it is difficult to tell by looking at the original sentence, try moving the who/whom in the sentence to see whether it holds an object position:

1) ...the Government has instructed Heads of Department to terminate whom from long-standing provisional employment.

2)...the Supervising Teacher considered whom deserving of compensatory remuneration...

3)...the academic committee had originally advised against whom...

4)...she had expressed reservations about whom in writing...

5)...the Supervising Teacher had specifically shown a reluctance towards nominating whom...

It may initially feel weird performing this kind of move operation, but if you can't immediately see whether the who/whom is acting as an object or not, then this is the easiest way to disambiguate that.

Relative pronouns like who, which, etc. are extracted from some position in the relative clause and moved to the front of the clause.
I.e,

• the car [which she saw ___ in the street]
  starts with a clause that modifies a noun phrase the car,
  that contains a noun phrase the car --
    the car [she saw the car in the street]
  then the car is changed to a relative pronoun (which), and moved to the front of the clause,
  leaving a conceptual gap (____) in the clause showing the original position of the NP.

That's the way it works in all cases, except for the case in which the NP is the subject of the clause. There's no movement then, because the subject is already at the beginning of the sentence; it just needs to be changed to a relative pronoun and we're done.
I.e,

• the dog [which barked in the night]
  comes from
  the dog [the dog barked in the night]
  and we're done. No movement, no gap.

Who and whom work the same way as which, but there's a complication.

Since Relative Formation is an unbounded extraction rule, the relativized noun phrase can come from any part of the relative clause, no matter how many subordinate clauses it has. That means the gap is not always easy to find, especially for a non-native speaker.
E.g, the relativized NP can be the subject,

• the man [the man told me yesterday the FBI was after him]
  ==>
  the man [who told me yesterday the FBI was after him]

but it can also be the object of a preposition several levels down

• the man [the FBI told me yesterday they were after the man]
  ==>
  the man [whom the FBI told me yesterday they were after ____].

In fact, it can be arbitrarily far down, and may be the subject of a predicate in another clause.

• the man [the FBI told me Mary said she thought the man was guilty]
  ==>
  the man [who the FBI told me Mary said she thought ____ was guilty].
  (whom is incorrect here because the man is the subject of was guilty)

When there is a preposition involved (as with advise against and reservations about), then Pied-Piping the preposition along with the relative pronoun can be employed to muddy the waters even further; it's an optional rule, but it can be employed whenever the relative pronoun is a prepositional object. This is the only construction in English that actually requires whom
(though, since pied-piping is optional, whom is still never required; just avoid pied-piping).
Viz.

• Mr.A, against whom the academic committee had originally advised,
• Mr.A, about whom she had expressed reservations in writing,

Executive summary: Find that gap, test it with he/him, and pied-pipe all prepositions.