Brake pads should last more like 35,000 miles, so in terms of pad life you are still fine.
Soft-feeling brakes would be caused by the lines more than the pads, so if yours don't feel soft then at least the lines are good.
If you have already tried cleaning and stopping harder a few times, I'm not sure what to tell you. Changing the pads might make it go away for a while, bit it will probably be back, especially with some pads. When I switched to EBC I could never get them to be quiet for long without stopping hard several times per trip. However, with Vesrah I never had that problem, plus they had better feel.