In both cases, it will not return. This is covered by rule 603.7c:
603.7c A delayed triggered ability that refers to a particular object still affects it even if the object changes characteristics. However, if that object is no longer in the zone it's expected to be in at the time the delayed triggered ability resolves, the ability won't affect it. (Note that if that object left that zone and then returned, it's a new object and thus won't be affected. See rule 400.7.)
Example: An ability that reads “Exile this creature at the beginning of the next end step” will exile the permanent even if it's no longer a creature during the next end step. However, it won't do anything if the permanent left the battlefield before then.
The Underworld will be able to track it to the first zone it goes to when it leaves the battlefield (most of the time, this will be the graveyard). However, if it leaves that zone before the delayed trigger resolves, it will not not be able to track it to the new zone. In the case of the Cerberus (or Academy Rector, since the Cerberus will prevent the Underworld from being cast) since it's in the exile zone, not the graveyard, it will not be returned. And in the case of Kozilek, since Kozilek and the sacrificed creature are in the library, not the graveyard, they will also not return.
EDIT: It's been point out that the Ceberus prevents the Return from being cast, which is true. But the main point of the question still stands (can the creature be returned if it's changed zones in the meantime). Change the Cerberus with something like Academy Rector and the answer still stands (the Rector will not be returned by the Underworld, since it's no longer in the graveyard).
Nathan Long
Wizard.Com Board NetRep
Edited Nathan Long (Oct. 13, 2013 12:43:14 PM)