מסכת עבודה זרה, דף לה עמוד ב explains how if one curdles milk with the sap of leaves from an orlah tree, the cheese is permitted. The reason is because the leaves are a separate entity from the fruits. Wouldn't the same apply to rennet and gelatin used as texture enhancements in foods?
The mishna Orla 1:7 states that only the fruit is prohibited with regards to Orla. Bartenura explains that Lev. 19:23 explicitly says es piryo, "its fruit." So the reason orla-sap-cheese is permitted is because the sap itself is kosher. Contrast with cheese made with rennet from a non-kosher-slaughtered cow, which is not kosher.