Thanks for the cc. I wasn't aware of this bug report.

The behavior makes sense, but is definitely undesirable. There are at
least two solutions:

1. Make `package-installed-p' and other functions automatically
   initialize package.el if necessary.

2. Call `package-initialize' unconditionally during startup.

Solution (1) might make package.el functions a little slower. But
solution (2) would definitely make startup slower for people who don't
use package.el.

Solution (1) seems like the correct way to do this. Is there any
reason it wasn't done already?

Any thoughts?