By any means, the inconsistency of apt-get's and aptitude's behavior should be a bug; either we make them all look for all packages - an approach not correct enough but doesn't lag; or speed up the procedure aptitude looks for available packages and apply it to apt-get too.