Ну для начала надо действительно постараться с оптимизировать код, для этого ничего переписывать не надо, надо только добавить пару строчек, которые помогут Excel'ю сосредоточится над работой а не заниматься ненужными фоновыми вычислениями и обновлением экрана:

With Application
.ScreenUpdating = False
.Calculation = xlManual
.CalculateBeforeSave = False
.EnableAnimations = False
.ErrorCheckingOptions.BackgroundChecking = False
End With

Если ScreenUpdating сам после работы макроса включится, то забыв после работы макроса поменять .Calculation = xlManual, придется лезть в настройки и выбирать там автомат. (тоже самое с EnableAnimations)

По поводу совместной работы вижу токо один выход при заданных начальных условиях: разместить файл в общедоступной папке и написать макрос, коорый будет лезть к этому файлу по сети, брать свой кусок данных, выполнять его и писать в ответ обратно в файл (Excel позволяет совместно работать с фйалом). Т.е. главная задача разобрать свои данные так, чтобы макроса могли независимо брать/обрабатывать разные куски данных....как это сделать...не видя твоих данных и макросов ничего посоветовать тебе невозможно, токо идея



P.S. а вообще все-таки стоит рассмотреть идею по переводу всех этих вычислений на другие программные рельсы. Я сам как-то с таким столкнулся, когда небольшая таблица в Excel'е выросла до 30 000 строк, лопатить которые Excel уже сильно напрягало.
Просто если используется Excel, значит идет работа с таблицами, а это прерогатива Баз данных. Я уверен на все 100 процентов, что все твои вычисления можно спокойно перенести в Access, который справится с твоим объемом шутя - у него работа такая :)