Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?
I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed.

Indices

You can build up an index for each word.  Build a hash table.  For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word.  This hashtable can be built up once in a linear scan of the set of dirty names (Set2).

Then, given a clean name, iterate over the words in the clean name.  For each word, look it up in the hash table, and iterate over all the dirty names that contain that word, and check how many words it has in common with the clean name.  Keep the best match.

This can be optimized a bit.  If the clean name contains a word that occurs in many dirty names, handling that word will be slow.  So, you could find the number of times each word occurs in some dirty name (its frequency) and store this in a hash table.  Then, given a clean name, you could iterate over the words in the clean name in order of increasing frequency, keeping track of the best match you've found so far.  If you've found a match of length $\ell$, then you can stop the iteration early without iterating over $\ell-1$ highest-frequency words in the clean name without missing any valid matches.

Tries

The order of words in a name is irrelevant, so sort the words in each phrase.  For instance, 'some good product' becomes 'good product some'.  Do this to each name in each set.

Next, build a trie to represent the set of good names (Set1).  For instance, in your example the trie will be

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+


Now, pick a dirty name.  We want to find a match for it from the trie.  I suggest you use a recursive algorithm to find all matches: to find a match for the name $w_1 \cdots w_n$ in the trie $T$, check whether there is an edge out of the root of $T$ labelled $w_1$, and if so, recursively find all matches for $w_2 \cdots w_n$ in the subtrie pointed to by that edge; also recursively find all matches for $w_2 \cdots w_n$ in $T$.  Once you have found all matches, keep the longest one.

For instance, for 'another very long product name', after sorting this becomes 'another long name product very'.  You look that up in the trie by recursively finding all matches for 'long name product very' in the subtrie +-- product --+, and by finding all matches for 'long name product very' in the main trie.

This search process can be optimized in various ways, e.g., by keeping track of the longest match found so far and stopping early if there's no way the recursive call could find a longer match based on how many words you've matched so far and how many words remain.

There's no requirement to sort by lexicographic order.  You can sort in any other order, as long as it is consistent.  For example, you could sort by the frequency of words in the entire dataset (into the least common words first), which might help reduce the number of recursive calls.