How to enforce a constraint over multiple tables?
This can easily be done by using cascading keys that overlap.  Here is an example using the Oracle Data Modeler (note there is a bug in this tool or a configuration issue as the Provider_Feature table should show each column as PF meaning both PK and FK):



In this example, the PK to Provider Product includes the Product Number provided, and the PK to Feature includes the Feature Number supported for that Product.  The Product Number in Provider_Feature is a FK back to both the Provider Product and the Feature.  The FK constraints thus prevent inserting a Provider Feature for a Product Feature combination not already instantiated as a Product Feature possibility.

This solution assumes that a feature is identified by a Product - that is a feature cannot exist outside the context of a product.  That assumption is likely valid as features, in and of them selves, have no meaning with the context of a product.  However, if you do want to instantiate features that can included on multiple products, then you simply add a Feature table and make the current Feature table a Product_Feature table.

Often database designers assume each table must have its own "identifier."  Nothing could be further from the truth.  Please see Fabian Pascal's excellent blog post on this topic.  Adding a surrogate Key to each table means the natural business rule you are trying to enforce can no longer be enforced declaratively via PK and FK constraints, just as you have found.  If you must have a SK for some reason your only option is to enforce the constraint procedurally using a trigger. This option is much more problematic.  First, you have to write, debug, test and maintain the trigger.  The book Applied Mathematics for Database Professionals provides excellent detail on how difficult it can turn out to be to express constraints using procedural logic in a way that performs adequately.  Secondly, triggers in and of them selves can sometimes be performance inhibitors as they execute serially.

My recommendation is to use the natural declarative approach.