Maybe you're using (use-package foo :ensure t) or something similar? I did that before, and if there was some package that simply wasn't available it would of course check and not find anything every time I started emacs. I don't use :ensure t any more (I check the elpa folder into git along with my init file for keeping it in sync across machines)