I'm confused. Sometimes, following 'pe', the definite article seems to be required and sometimes it doesn't. Does this have something to do with the presence or not of a modifier - in this case 'nostri'?
That's correct, the pronominal adjective "noștri" makes it necessary to have an article. You can drop the enclitic article and use the possessive one instead: "noi îi lăudăm pe ai noștri părinți", though it sounds less natural.