Have you tried using the Pencil tool instead of the Brush? The difference between the two is the Pencil applies no antialiasing to your strokes, so if it's a filtering problem, that should reduce or eliminate it.
And following on from RobA's idea, you can change Photoshop's default interpolation method in Edit > Preferences > General. Try Nearest Neighbor to start with. If it is an interpolation issue, then that will make the brush nice and crisp, but it will probably also distort the edges a bit.
Let us know if either or both of those methods improve things or not.
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!