I've found solution on my own. I'll post it as someone else may encounter similar problem and it can save him hours/days of investigation.
What i did to find solution?
I've analyzed test application (basically only one line where new excel application is being created) with Process Monitor and it didn't show anything important. Then I repeated analysis with newly started Excel process. It highlighted numerous reads of windows registry
HKEY_USERS\S-1-5-21-2929665075-1795331740-364918325-1024\Software\Microsoft\Office\15.0\Excel\Resiliency\DocumentRecovery
Under above location I've discovered tens of thousands of keys. They all were created by Excel's "auto-recovery" functionality. Because of the numbers, loading them when starting new Excel object was taking about 40 seconds. This number was additionally being multiplied by another 10-20 simultaneously loaded sessions (did I mention my application is running on 20 user sessions?).
Solution: Removal of "Resilency" registry tree does the trick.
Why all these "auto-recovery" entries were there in a first place? I guess I don't handle closing of Excel very well and it "thinks" I'm having regular crashes and "tries" to help.
Now what's left is preventing it from happening all over again. I'll have a closer look at my ExcelClose() function.
Thanks for your attention - Adrian