I had the same issue a few years back - some of my suggestions:-
- Merrell All-Out Rush is a good trail shoe with a totally soft back.
- Most of the InnoV-8 range has a fairly soft heel counter if you're in the UK
- Nike Free as you've mentioned is good.
- A lot of the new New Balance shoes are coming out without a heel counter - if you can get to look at them in store. It's a sort of weird soft, ridged material they're using. It's good. I think they're marketing them under the Vazzee Pace and Race shoe names.
- Skechers Kinvara has one but depending on the model it's quite soft.
- Adidas Galaxy Elite isn't a shoe I'd use for serious running but meets your criteria.
Hope that helps.