COMException 0x800706BE when trying to use MAPI namespace object (Outlook)

I am trying to write code using C# that automates Outlook to send emails and check the shape that they arrive in, as part of the test suite for an Outlook plugin product.

The code seems to work fine on my development environment (A VM running Win 8.1 x64, Outlook 2013 x64 and VS2013) if outlook was started before I start the tests, but in many other cases, it crashes with the COM Exception as mentioned in the title. For example:
In the "live" test environment, which is theoretically identical to the dev environment (The dev environment was cloned from the live test environment, then I installed VS2013), it crashes in all cases.

I made a stand-alone console project to exhibit the issue, which I will paste below.

The line of code that always throws the exception is this:
Outlook.Recipient r = MAPI.CreateRecipient(SMTPAddress);

Where MAPI is an Outlook Namespace object:
oApp = new Outlook.Application(); MAPI = oApp.GetNamespace("MAPI");

We tried getting oApp via Marshal:
oApp = Marshal.GetActiveObject("Outlook.Application") as Outlook.Application;

But this does not seem to fix the problem.

The below code attempts to send email from an "internal" Exchange account to an "external" (eg gmail) account (Both of which should be present as accounts in the Outlook client), then work out which folder the email is expected to arrive in purely from the SMTP address of the recipient.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using Outlook = Microsoft.Office.Interop.Outlook;
using System.Threading;
using System.Reflection;
using System.Runtime.InteropServices;

namespace MAPI_Repro
{
    class Program
    {
        static void Main(string[] args)
        {
            var mapiTest = new MAPI_Test();
            mapiTest.DoTest();
        }
    }

    class MAPI_Test
    {
        public Outlook.Application oApp;
        public Outlook.NameSpace MAPI;
        public static int OutlookMajorVersion;

        [DllImport("user32.dll")]
        public static extern bool ShowWindow(int hwnd, int nCmdShow);
        public void DoTest()
        {
            // Test configuration
            string IntSMTP01 = "exchangeuser@yourdomain.local";              // Address email is sent FROM
            string ExtSMTP01 = "testaccount@outlook.com";    // Address email is sent TO
            bool SetSendUsingAccount = false;    // True = Set mail to come from EXTSMTP01 account
                                                // False = Use Outlook default account
            bool UseMarshal = true;    // True = use "Marshal.GetActiveObject" to get Outlook.Application object
                                        // False = just use "new Outlook.Application()"
            bool SendEmail = true;     // Whether or not to send an email as part of the test.
                                        // Code never seems to crash if email is not sent. 

            // End Test configuration

            Debug.WriteLine("DBGVIEWCLEAR");
            Dictionary<int, string> OutlookVersionNames = new Dictionary<int, string>()
                {
                    {7, "97"}, {8, "98"}, {9, "2000"}, {10, "XP"}, {11, "2003"},
                    {12, "2007"}, {14, "2010"}, {15, "2013"}, {16, "2016"}
                };
            Process process = null;
            Process[] processes = null;
            int count = 0;

            processes = Process.GetProcessesByName("OUTLOOK");
            count = processes.Count();
            Log("Outlook process count is: " + count);
            if (count != 0)
            {
                // If count is non-zero, it should always be 1, as Outlook is a Singleton
                // If the process' HWND is 0, it is "dead", so terminate it.
                if (!processes[0].HasExited && (int)processes[0].MainWindowHandle == 0)
                {
                    Log("Killing dead Outlook process.");
                    processes[0].Kill();
                    processes[0].WaitForExit();
                    Log("Process quit");
                }
                else
                {
                    // "Live" outlook process found, use this process
                    process = processes[0];
                    Log("Using live Outlook process with HWND " + process.MainWindowHandle);
                    // Make sure the window is visible (Not minimized)
                    ShowWindow((int)process.MainWindowHandle, 9);
                }

            }

            // Start new Outlook process if required
            if (process == null)
            {
                Log("Starting new Outlook process");
                // Fire up the new process
                process = Process.Start(new ProcessStartInfo("outlook.exe"));

                Log("Waiting for Outlook splash screen to appear");
                // Wait for the new Outlook process to get a Window Handle (HWND)
                // This will be the HWND of the Splash Screen
                while ((int)process.MainWindowHandle == 0)
                {
                    Thread.Sleep(100);
                }
                Log("Waiting for Outlook splash screen to disappear");
                while (true)
                {
                    // Get process by name
                    Process p = Process.GetProcessesByName("OUTLOOK")[0];
                    // Does the process we just got using the same name have the same HWND?
                    if (p.MainWindowHandle != process.MainWindowHandle)
                    {
                        // No. Splash Screen disappeared.
                        process = p;
                        break;
                    }
                }
                Log("Outlook main window has appeared, and has HWND " + process.MainWindowHandle);
            }

            // By this point, there should be an instance of Outlook running.
            // Next, we try and get the Outlook.Application COM object
            //Thread.Sleep(60000);

            if (UseMarshal)
            {
                Log("Getting Outlook.Application using Marshal.GetActiveObject");
                while (true)
                {
                    try
                    {
                        // This FAILS while ANY of the following are true:
                        // 1) Outlook is the active application.
                        //    As soon as you hit ALT-TAB, click another app, or minimize the window, then this succeeds.
                        // 2) Outlook has recently started and is not settled.
                        oApp = Marshal.GetActiveObject("Outlook.Application") as Outlook.Application;
                        Log("Marshal.GetActiveObject SUCCESS");
                        break;
                    }
                    catch (System.Runtime.InteropServices.COMException exp)
                    {
                        Log("Marshal.GetActiveObject FAILED, retrying...");
                        // Minimize the window
                        ShowWindow((int)process.MainWindowHandle, 6);
                        // Restore the window
                        ShowWindow((int)process.MainWindowHandle, 9);
                    }
                    Thread.Sleep(100);
                }
            }
            else
            {
                Log("Getting Outlook.Application object using new Outlook.Application()");
                oApp = new Outlook.Application();
            }

            // Set-up complete.
            // By this point, we have the Outlook.Application object that is used throughout the rest of the code.

            string v = oApp.Version;
            if (v == null)
            {
                throw new Exception("Could not get Outlook version");
            }
            OutlookMajorVersion = Int32.Parse(v.Split('.')[0]);
            string OutlookVersionName = OutlookVersionNames[OutlookMajorVersion];
            Log(String.Format("Outlook version is {0} ({1})", OutlookMajorVersion, OutlookVersionName));

            Log("Testing MAPI ==============================================================================");

            MAPI = oApp.GetNamespace("MAPI");
            MAPI.Logon("", "", Missing.Value, Missing.Value);

            if (SendEmail)
            {
                Log("Creating email...");

                Outlook.MailItem mail = oApp.CreateItem(Outlook.OlItemType.olMailItem) as Outlook.MailItem;
                mail.Display();
                mail.To = ExtSMTP01;
                mail.Subject = "MAPI Test ";

                if (SetSendUsingAccount)
                {
                    // This code seems to increase the likelihood of a crash
                    // However, it is not required to repro the primary issue I am trying to solve
                    Log("Setting SendUsingAccount...");
                    Outlook.Account acct = GetAccountFromSMTP(IntSMTP01);
                    if (acct == null)
                    {
                        Log("ACCOUNT IS NULL, QUITTING");
                        return;
                    }
                    mail.SendUsingAccount = acct;
                }

                Log("Sending mail...");
                ((Microsoft.Office.Interop.Outlook._MailItem)mail).Send();
            }
            // THIS PART IS WHERE OUTLOOK TENDS TO CRASH
            Log("Trying to execute MAPI.CreateRecipient...");
            Outlook.Recipient r = RecipientFromSMTP(ExtSMTP01);

            // If code gets this far, it does not crash afterwards.

            Log("Expected delivery folder is: " + GetDeliveryFolder(ExtSMTP01).FolderPath);

            Log("END TESTING MAPI ==============================================================================");

        }

        // vvvvvvvvvvvvvvvvvvvvvv THIS IS THE CODE THAT THROWS AN EXCEPTION vvvvvvvvvvvvvvvvvvvvvvvvvvvv
        /// <summary>
        /// Returns an Outlook Recipient object, given an SMTP address string
        /// </summary>
        /// <param name="SMTPAddress">The SMTP address of the account to look up</param>
        /// <returns>An Outlook Recipient object for the SMTP address, or null on fail.</returns>
        public Outlook.Recipient RecipientFromSMTP(string SMTPAddress)
        {
            Log("Getting Recipient");
            Outlook.Recipient r = MAPI.CreateRecipient(SMTPAddress);
            if (r == null)
                return null;
            r.Resolve();
            return r;
        }

        /// <summary>
        /// Gets an Outlook Account object from an SMTP address
        /// </summary>
        /// <param name="address">The SMTP address</param>
        /// <returns>An Outlook.Account object for that address</returns>
        public Outlook.Account GetAccountFromSMTP(string address)
        {
            Outlook.Accounts accounts = oApp.Session.Accounts;
            foreach (Outlook.Account this_account in accounts)
            {
                address = address.ToLower();
                var addr = "";
                if (this_account.SmtpAddress == null)
                {
                    // Outlook 2007 does not seem to work with SMTPAddress property. Use DisplayName instead.
                    addr = this_account.DisplayName;
                }
                else
                {
                    addr = this_account.SmtpAddress.ToLower();
                }

                if (addr == address)
                {
                    return this_account;
                }
            }
            return null;
        }

        /// <summary>
        /// Given an SMTP address, returns a folder object where the mail is expected to arrive
        /// </summary>
        /// <param name="AccountSMTP">The SMTP address to which the mail that was sent.</param>
        /// <returns>An Outlook.MAPIFolder object for the folder that the mail is expected to arrive in.</returns>
        public Outlook.MAPIFolder GetDeliveryFolder(string AccountSMTP, int RecipientIndex = 0)
        {
            Outlook.MAPIFolder return_folder = null;
            Outlook.MAPIFolder tmp_folder = null;
            string ExpectedFolderName;
            Outlook.Recipient recipient;

            recipient = RecipientFromSMTP(AccountSMTP);

            // Decide what name we are expecting for the folder. Version 12 = Outlook 2007
            if (OutlookMajorVersion == 12 && recipient.AddressEntry.AddressEntryUserType == Outlook.OlAddressEntryUserType.olExchangeUserAddressEntry)
            {
                // Outlook 2007 - folder name is User name (eg "Peter Jones")
                ExpectedFolderName = recipient.Name.ToLower();
            }
            else
            {
                // Other versions of Outlook - folder name is SMTP address.
                ExpectedFolderName = AccountSMTP.ToLower();
            }

            // Find the folder
            //for (var i = 1; i <= oApp.Session.Stores.Count; i++)
            for (var i = 1; i <= MAPI.Stores.Count; i++)
            {
                //Outlook.Store store = oApp.Session.Stores[i];
                Outlook.Store store = MAPI.Stores[i];
                if (store.DisplayName.ToLower() == ExpectedFolderName)
                {
                    //tmp_folder = oApp.Session.Stores[i].GetRootFolder();
                    tmp_folder = MAPI.Stores[i].GetRootFolder();
                    break;
                }
            }

            if (tmp_folder == null)
                goto failed;
            return_folder = tmp_folder;
            tmp_folder = null;

            // Navigate to the Inbox
            for (var i = 1; i <= return_folder.Folders.Count; i++)
            {
                Outlook.MAPIFolder f = return_folder.Folders[i];
                if (f.Name == "Inbox")
                {
                    tmp_folder = f;
                    break;
                }
            }
            if (tmp_folder == null)
                goto failed;
            return_folder = tmp_folder;

            return return_folder;
        failed:
            Log("No folder found.");
            return null;
        }

        /// <summary>
        /// Prepends a string to a Debug.Writeline, for easy filtering in DebugView
        /// </summary>
        /// <param name="text"></param>
        void Log(string text)
        {
            Debug.WriteLine(String.Format("MAPI TEST: {0}", text));
        }

    }

}