If you do need the contact id's, you would need to pull them from the Contact Collection API, which will pull 50 at a time. The reason this works this way is that bulk exporting exports the files in the same manner that exporting from the user interface does, and exporting from the UI does not give contact ID's.
The only other work around that I can think of would be to not store the contact ID's on your end, but when you need the contact ID you can do a search by email address.
Thanks for the feedback Benjamin. We want to avoid doing searches by email address in case our users specify separate email address for our own contact records and for your mailing lists. We figured the CC ID was probably the most stable way to link our records with yours.
I suppose we'll just have to hit the Contact Collection API then. Thanks again for your time,