Missing Contacts from Mailing Labels in Civi 4.4
How are you trying to reproduce the problem? Are you just running a search and comparing the number of labels to the number of results?  If so, you should expect to have fewer labels because CiviCRM will automatically exclude contacts with "do not mail".

If that's not the issue, try looking at what shared attributes the excluded contacts have. If it is a bug, an important step to replicate and fix the issue is to know what kinds of contacts go missing (or alternatively if it's a new random group dropped on each search run).