Here is one solution, assuming your "Key" values are greater than 9000, and the other column values are not (more generally speaking, assuming there is no intersection between "Key" and other columns).
Join all columns in just one unique line using the text editor NotePad++. See here, how to do it.
Then, transpose this unique line to one unique column. For example, transpose on column B, starting on cell B3. Then, type on cell A3:
=IF(B3>9000,"Delete This Row",IF(OFFSET(A3,-1,1)>9000,OFFSET(A3,-1,1),""))
Drag the formula down to all rows in column A where there are data on column B.
It should yield a result similar to this:

Alright, now filter column A by "Delete This Row" values and delete all filtered rows.