I tested 30 HD titles w/o 5.1 sound at random, and all of them had 1080p encodes. My conclusion is that the vast majority of HD titles have them (someone pointed out that only about half of the recent HD anime additions have "X-High/HD" encodes, so not all). I could be wrong--I'm not testing 2000+ HD titles to make sure .
My guess is that they created 1080p encodings for almost all of the HD library before rolling out the disc-free PS3 player. I'd first thought that titles with 1080p encodings would turn out to be a subset of titles with 5.1 sound, but it appears to be the other way around. So far 5.1 sound seems to be running about 20% of HD titles.