Here's what I think is going on:
I observe two events in two different threads for the start and end of each print job. With some debugging and logging I recognized that FindNextPrinterChangeNotification doesn't always return only the two distinct events I've notified for, but some 0-events in general. In those cases FindNextPrinterChangeNotification returns 0 as the events in pdwChange. If I print a simple text file using notepad.exe I only get one event for creation of the print job with value 256 for pdwChange and the data I need in notifyInfo to compare my printed file name against and comparing both succeeds. If I print a pdf file using current Acrobat Reader 11 I get two events, one has pdwChange as 256, but gives something like "local printdatafile" as the name of the print job started, which is obviously not the file I printed. The second event has a pdwChange of 0, but the name of the print job provided in notifyInfo is the file name I used to print. As I use FreePDF for testing pruproses, I think the first printer event is something internal to my special setup.
The notifications for the deletion of a print job create 0 events, too. This time those are sent before FindNextPrinterChangeNotification returns 1024 in pdwChange, and timely very close after the start of the print job. In this case the exactly one generated 0 event contains notifyInfo with a document name which equals the file name I started printing. After the 0 event there's exactly one additional event with pdwChange of 1024, but without any data for notifyInfo.
I think Windows is using some mechanism which provides additional notifications for the same event as 0 events after the initial event has been fired with it's real value the user notified with, e.g. 256 for PRINTER_CHANGE_ADD_JOB. On the other hand it seems that some 0 events are simply fired to provide data for an upcoming event which then gets the real value of e.g. 1024 for PRINTER_CHANGE_DELETE_JOB, but without anymore data because that has already been delivered to the event consumer with a very early 0 event. Something like "Look, there's more for the last events." and "Look, something is going to happen with the data I already provide now." Implementing such an approach my prints now seem to work as expected.
Of course what I wrote doesn't fit to what is documented for FindNextPrinterChangeNotification, but it makes a bit of sense to me. ;-)