Do you have Analytics installed on every single page? I tripped over a similar issue in Piwik after realizing that "direct entry" doesn't always mean direct entry. It can also mean that the person came from any page elsewhere on my site that doesn't have analytics code. In my case it meant I had to add the code to the front page, which functions purely as a transfer point so there's no point in tracking it for its own sake.
Picking out non-robot visits with blank referer is the right way to do it. Depending on your server and other obscure variables it might come through as either "-" or a completely empty "" so make sure you're getting both. You may also need to screen for spaces on both sides of "" to get rid of search queries containing literal question marks.