I already tried the pencil tool, but I loose too much details when using it. Changing the default interpolation seems to have little effect. Funny thing is, sometimes when I do longer strokes, some of the hills are perfect and crisp while most of them are still blurred.

I helped myself by applying a non visible noise and creating all brushes with the size of 64 pixel. That makes the brushes a little awkward to use, but they are as crisp as they are supposed to be. I guess size matters after all

Thanks for all the good advice!