Some theoretical ideas which may work based on what information is available to you
Offline to their known billing address
It sounds like this is a commercial service. For some users, if they are using a personal credit card, etc. you may be recording their person billing information - you could send an offline reset code via postal mail to those users (like when a bank sends you an ATM pin). That would be slow, but hopefully there isn't someone someone snooping in the user's postal mail.
Re-verify the Credit Card on file with Card Security Code
If the use is using a personal CC, I have a theoretical scheme I will share below. I was thinking about Address Verification System, but I do not believe that requires the card security code (e.g., CVV) in general. Consider this process:
Request the user to make a small purchase on your site with the same credit card they had on file - maybe something like $.50 (you can offer to reverse this charge immediately after the verification or call it a special reset fee)
Then make the payment using the same billing information, credit card number that is on file. While the billing information may be easily research for a given individual, the credit card number should be hard to pull out of no where, and the card security code even harder.
This could be fairly automatic and validates against information you have on file.
Links to other identities
Let's say that your service allows users to enter in a social network profile into their account. Since this is a business tool, maybe you ask them for their LinkedIn profile for no reason at all, or maybe for an actual purpose to post their achievements on their timeline. Maybe you have a setup where you automatically tweet the courses a user completes, etc. Since the user entered her social media information into her profiles, you can ask her to validate through the social media service.
I recall Stack Exchange doing this at some point to merge two of my profiles, you put some type of message in profile of both accounts and then contacted an admin to do the merge. In your case, you can just private message the account the user had listed in her profile since its unlikely she would have added some random person's account on her profile on your site.
If you wanted to take on more risk, you could ask a user who never entered a social media profile before losing his old email to provide you with a few social media profiles and do some due diligence to see if those profiles seem legitimate (has real friends/followers from the same company the person used to work for). You can then requires at least two good profiles, ask them to put some update on the site or in their profiles to prove they own the sites or direct/private message them on both platforms to make sure they own them.
In the end, I assume the reason they would not just make a new profile is because they are paying for the service and they want that for which they have already paid. As they say, follow the money... However, this will not work if they used a corporate card they no longer have access to. Maybe they have an old copy of an invoice or credit card statement they can send to you in that case, is not very likely someone else outside of payroll/reimbursements has these types of documents. I would say if you can't do something with billing information, then maybe try the route of social media I described above.
I do not think you will easily be able to create a secure and robust platform to do this automatically, but I would also imagine you will not have hundreds of these cases a day. I would try to start with the most reliable and then work down on an individual basis to what is less reliable or more time consuming.
Thoughts on other strategies
It looks like the path you are going with right now and suggested in many of the other answers rely on taking in additional identification information at sign-up (ideally) and then using that information to later validate user when she no longer has her email account. The problem is that any of the information you are likely going to collect can be researched or found. You may run into a UX problem (why so many fields, why are you invading my privacy, etc.) if you start asking for a lot of information which is not relevant to your service. If you ask them to validate a lot of information it increases difficulty, but it doesn't sound like this will meet you requirements for reasonable assurance. The same issues apply with security questions.
Some of the other answers rely upon the user validating their identity by previous actions taken on the site. Depending upon your services this may be possible, but in many cases the actions could be difficult to remember, too much activity may be publicly known, or may be generic enough that any other user could impersonate the user. There is some potential with this path depending on your specific circumstances.
Other suggestions include asking for something that the user will carry with them such as a secondary email or a mobile phone (assuming they don't also give you the corporate mobile phone number). Any other type of token, hash, file, etc is probably a moot point if they are using their corporate email they are probably using their corporate computer and won't have access to this if they no longer have access to their corp email.
I see some of your questions related to SMS and availability on all user phones. Going on the assumption you have their personal phone and not their work phone, there are non-SMS based solution that use a VRU/IVR etc to give a code via voice. If you have a valid, accessible phone number then you should be able to contact that number via SMS or a voice prompt system. At the very least, at low volume, you could have a human call the number on file when a request is made. Hopefully there is not a high volume of users who moved on and forgot their password on a daily basis.