There is little you can do about this. The document has be at a stage where all the relevant links are present, otherwise the script can't find them and therefore can't set them up for shadowbox. The whole point of the various 'DOM Ready' techniques is to attempt to run a script at the earliest possible time when the document should be fully populated with all elements that might be targeted by that script. If you run without the 'DOM Ready' (or window.onload, whatever) then your page elements probably won't have been placed in the DOM and therefore won't be picked up by the shadowbox intialisation.
Or, you could put an onclick on every relevant link, that effectively disables that link.
Either way, you need to be able to show the links, or remove the onclicks, once shadowbox has initialised (or if it fails to initialise for whatever reason).
A third possibility might be to investigate the other libraries and see if any one out-performs the others in terms of 'DOM Readiness' (or maybe even window.onload ... but I doubt it very, very much!), but I'm not sure that you'll be able to find much of a difference.
I would suggest that it is probably better for any over-eager user to miss out on a fancy effect (of which you might justifiably be rather proud), but still end up seeing the content you want them to see ... rather than be frustrated by being told they can't click certain links yet, or put off by having extra links suddenly appear all over the page.
Combine literacy with curiosity and a whole world of information opens up to you