We had a requirement to delete few of the components from the solution and we followed the new feature that is now available for this in product, starting from CRM 2016 Update 1.
However, we ran into the following error while trying to apply solution upgrade i.e. Solution with ID does not exist.
First time it worked properly and deleted the components from the TEST environment. Then we removed few more components and tried applying this updated solution again to remove those remaining components from our TEST environment, that is when we got this issue.
The issue happens because of certain orphan records which still exist in the database and references the old deleted solution.
Below is the fix for this issue (i.e. update those records in the database).
However as in our case, as it was online we ended up creating the product support ticket to do the same
Hope it helps..