As long as it is a managed program then, yes, you can run it in its own AppDomain.  You'll need a thread to run the code, AppDomain.ExecuteAssembly() is the handy one that automatically starts running the Main() method of that program.  Here's an example that uses two console mode applications:
using System;
using System.Threading;
using System.IO;
namespace ConsoleApplication1 {
    class Program {
        static void Main(string[] args) {
            string exePath = @"c:\projects\consoleapplication2\bin\debug\consoleapplication2.exe";
            for (int ix = 0; ix < 10; ++ix) {
                var setup = new AppDomainSetup();
                setup.ApplicationBase = Path.GetDirectoryName(exePath);
                var ad = AppDomain.CreateDomain(string.Format("Domain #{0}", ix + 1), null, setup);
                var t = new Thread(() => {
                    ad.ExecuteAssembly(exePath);
                    AppDomain.Unload(ad);
                });
                t.Start();
            }
            Console.ReadLine();
        }
    }
}
And the one that's ran 10 times:
using System;
namespace ConsoleApplication2 {
    class Program {
        static void Main(string[] args) {
            Console.WriteLine("Hello from {0}", AppDomain.CurrentDomain.FriendlyName);
        }
    }
}
One thing I didn't count on and stuck under a table a bit, the AppDomainSetup.ApplicationBase property didn't work as I expected.  I had to pass the full path of the EXE to ExecuteAssembly() instead of just passing "consoleapplication2.exe".  That was odd.