You can omit "should" in this phrase because "recommend that" takes the subjunctive mood in formal, proper English. In other words, one writes "I recommend that you be on time," or "I recommend that he do this first." In everyday speech, however, the subjunctive mood can sound a little "stuffy" and "snobby" so one way to get around this is to use the modal "should" to replace the verb in the subjunctive.