Enabling document id on a hierarchy of sites is not as straight forward as one should think.
I have digged pretty deep into this one more than one occasion (might collect it to a blog post later), and it all boils down to the SPWorkItems that the timer job uses to enable document id on the sites/subsites and the timer job that sets the document id on each document.
One of the things that the work items look for, is how large the site collection is. A site that has more than one subsite, more than 20 lists (stupid since docid doesnt even support lists) and 40 document libraries (might be the other way around, i forget) is considered "a large site". If a site is large the work item is delayed for 30 seconds (which is also kind of weird, since that only would postpone any impact on site performance, and because the timer jobs that pick up the work items only run once a day anyhow!).
So basically since the timer job runs once a day, it can literally take weeks for a document id to be fully propagated.
There are several approaches here, but a simple one is to set the document id timer jobs (Document Id Assignment job and Document Id enable/disable job) schedule to something low, like 5 minutes or even less, and then trigger a document id enabling by going to _layouts/DocIdSettings.aspx and reset the document id prefix. This will trigger a chain of work items. This will take time even though you have set timer jobs to run frequently, due to the +30 minutes delay on "large sites" (there are ways to set the date directly in the database, but since that is unsupported I will not dig further into that here).
Then wait.... and wait... and wait even longer. I enabled Document Id for 3 site collections where one had approximately 50 sites and 300 documents. This took 3 full days with 5 minute interval on timer jobs (and me occasionally setting the work item to "now" instead of +30 minutes).
Note: DONT try and play around with some of the DocumentId methods in the API that are public but named InternalXXX. Calling these will render your site collection unusable for Document Id's as some of the docid properties that are written on SPWeb property bags will get out of sync. Trust me on this, I tried and messed up an entire test site ;-)