As I hinted at in my comment, I would use the rewrite API to handle this, specifically by adding a rewrite endpoint. That way you don’t have to deal with working out what’s an actual 404, and what’s a request for one of your dynamically generated pages. It doesn’t give you exactly the URL structure you have in your question, but I think it’s a reasonable compromise in this case.
First we add the rewrite endpoint. In this example I’ve used type, so your URLs would be /fruit/type/orange/:
function wpa_rewrite_endpoint(){
add_rewrite_endpoint( 'type', EP_PAGES );
}
add_action( 'init', 'wpa_rewrite_endpoint' );
Now within your template, you can check if type has been set and you’ll know to fetch that keyword from your webservice:
if( $requested_type = get_query_var( 'type' ) ){
// pass $requested_type to webservice
}
You also might want to look into the Transients API for caching the data locally, if you get a lot of hits and the extra http requests are slowing things down.