1. The mayor ordered that the man (should) leave the city early.

2. He suggested that the party (should) be put off.
3. He insisted that she (should) make a sppech.
4. They demanded that he should resign.
4-1. They demanded that he resign.
4-2. They demanded that he not resign.
4-3. They demanded he not be resign.
---------------------------
Are they all grammatical? In American English, is 'should' omitted? Can we omit 'that'? Is #4-3 correct? (Thank you for yoiur help.)

4-1 and 4-2 are correct although 4-2 is unlikely.

4. and 4-3 are incorrect.

Damon is correct.

Sentences 1-4 include dependent clauses beginning with "that" which have verbs in the subjunctive mood. The auxiliary verb "should" is not to be included.
http://grammar.ccc.commnet.edu/grammar/verbs.htm#mood

In American English, it is more common to omit "should" in sentences like the ones you provided. Therefore, the correct versions would be as follows:

1. The mayor ordered that the man leave the city early.
2. He suggested that the party be put off.
3. He insisted that she make a speech.

Regarding "that," it is generally not omitted in formal writing. However, in informal spoken English, it is often dropped. So, both versions with and without "that" can be considered grammatical, but including "that" is more formal and preferred in written English.

Now, let's talk about the fourth sentence and its variations:

4. They demanded that he resign.
4-1. They demanded that he not resign.

Both versions 4 and 4-1 are correct. In a negative context, you can use "not" after the verb "demand" to express an opposite expectation. However, version 4-2, "They demanded he not be resign," is not correct. The verb "be" should not be used in this context.

In summary, all the sentences are grammatically correct except for 4-3, which should be revised to either 4 or 4-1 depending on whether you want to express a positive or negative expectation.