I'd say they're both correct. But in 1 the people you advise can be different from the people who need to be learning the lesson ("The headmaster advised (in a note to the teachers) that they (the pupils) should learn their lesson"). Whereas in 2 the people being advised are the same as the ones learning the lesson ("the teacher advised them (the pupils) to learn their lesson"). d
Yes, both are grammatically correct. The "should" is not always necessary, but I think it adds some emphasis. I agree, however, that the second sentence sounds more natural.
It's funny that "advise someone to do something" is more common than "advise that someone do something", while the opposite is true for "recommend someone to do something" and "recommend that someone do something" (th