Digital BW, The Print

So I've been running a lot of tests today, and here's what I've found -

It seems that I can print a "true" black, and excellent midtones, but
that I can't print a really deep deep shadow-grey. So what happens is
that places on my RGB file that are, say, R5 G5 B5 print a grey that's
too light to blend evenly into the dots of pure black beside them - so
I get blacks that look posterized and/or dithered. 

My midtones are very very good - the only posterization and dither I
am getting is in the "real" blacks. 

My histograms are (I think) pretty good.

I _do_ see some dither from around a 0/0/0 black to a 10/10/10 grey in
my blackest shadows, so that's certainly contributing - but it looks
very natural on screen, and much much more pronounced in the prints. 

My step-wedges seem good

Is this a histogram/scanning problem in my files? If so, what's the
best approach to fix it - do I need noise-free shadows?

Thanks :)

-Charley