BeginInvoke uses threads spun up from the ThreadPool. You may have noticed that under certain circumstances, it seems as though the asynchronous threads are slow to spin up, and sometimes some of the method calls in a series of calls to BeginInvoke may not start until other calls complete. This is due to the amount of time it takes for a thread to be created in the ThreadPool.
A simple way to fix this is to increase the minimum number of available threads in the threadpool by calling ThreadPool.SetMinThreads.