virtualbox NS_ERROR_FAILURE (0x80004005)

I had similar issue on xubuntu 18.04 where my Virtualbox guests was to run windows 7. Although I had Virtualbox 5.2 installed previously that worked.

1. I made sure that virtualbox-dkms was installed by running this command:

   dpkg -l | grep virtualbox-dkms
   

2. Then I purged it and and reinstalled only dkms:

   apt-get purge virtualbox-dkms && sudo apt-get install dkms
   

3. Then I ran the suggested command to rebuild the kernel:

   sudo /sbin/vboxconfig 
   

This is what worked for me.

After a long, friendly and fruitful chat with @DavidFoerster, it turned out that Microsoft and its weird update policy was the culprit!

David patiently guided me through the reinstallation of the VirtualBox packages from the Ubuntu repositories and check out the configuration (dkms, extension packages, etc.). At last, he asked me to try a new installation with a live ISO. It was then that I noticed that my "Default Machine Folder" defined in VirtualBox - File - Preferences - General was not usable. I knew that it was on a mounted NTFS used by the dualboot Win10 system. A closer look showed that at present it was mounted read-only, which prevented the virtual machines from starting (with a not very helpful error message).

As I recalled then, shortly after I had last successfully booted the VirtualBox guests, I had not only got Ubuntu updates, but I had also booted for the first time since long my native Win10 system. Apparently, Microsoft had then installed updates AND had reactivated the 'fast startup' option (which certainly had been deactivated before!) - so that later, back in Ubuntu, the NTFS file system was mounted in read-only mode, as Windows had not properly shut down.

Now that I have again deactivated the 'fast startup' option in Windows10, my guest systems are running again.

Thank you, David, for asking the right question which set me on the right track!