Oren,
It is always best if you post examples with EXIF attached so we can help. It could be so many things.
One thing you might check: Is your dial set to spot focussing or auto? In spot mode, the camera focusses where you point it. In Auto, the camera has to decide what to focus on. It could be the closest object, it could be something in the scene with alot of contrast. You just don't know for sure. (I just don't know why anyone would use auto mode).
One other thing: Sharpening does not add detail. It only highlights the detail that is there. I disagree that the k10d "naturally shoots soft." You must have been reading DPReview.
When I do jpeg conversion if I am using the Pentax Photo Lab, I use "Natural" tone. That is exactly the same as setting the camera to "Natural". I find that setting most closely resembles what I see in the viewfinder. On another thread, I just posted some comparisons at high iso of my k10d and k20d. Take a look at the k10d shots. They were jpeg converted on "Natural" which has a -1 sharpening by default! The photos are very "sharp" with alot of detail:
k10d vs k20d ISO 1600 - a set on Flickr
Click on "all sizes" and "original" and look at the detail of the cottage for example. Or the "bricks" on the picture frame.