Making the elements in the multi instace subprocess async did work, indeed. However, it seems that there is still a timeout due to a lot of write queries to the Activiti history tables, which all seemed to happen in 1 transaction.
We solved this problem, by not starting 1 process which starts 1500 muli-instances, but by starting the 1500 multi-instances ourselves in a transactionless EJB.
Thank you for your reply!