Huh. Well, that's the solution I usually use, but I don't make many low-poly models. You mentioned a cube, so I tried a few things with that and it looks like the cube's vertex normals are projected at an angle from the adjacent faces, like so:
But if the side faces are deleted and the normals recalculated (Select all->Ctrl+N), the normals change to what you have:
I would try creating a face between the two edges you're having trouble with, recalculate the vertex normal and then delete the face. It's time-consuming, but if you really want to save on poly count I guess it's worth it.
I have CDO. It's like OCD, but the letters are in alphabetical order, like they should be.