Not sure why it would be random, but here are a few things to check;
Go into your app drawer and open Downloads and check that the files are indeed downloading. There could be an error or other issue with the download and these errors sometimes do not notify you that the task failed.
Go into your Gallery app and open the menu and go to Show/Hide Albums and check that the folder Downloads is visible to your gallery. This assumes that you are printing from the share feature in the gallery.
Download a file manager if you do not already have one, Astro and ES are quite popular but there are hundreds more. Then browse to SD>Download or SD>My Documents>Download and ensure that the files are there. You may have more than one download folder so be sure to check them all. With the file manager you can also just search for the file by name if you can recall any portion of the title and try to print it from there. Astro offers this print feature not sure of ES or others. Also if you are using an Epson printer there is a very nice Epson app at the Google Play.
Post back if you need more assistance.