I have found a solution / workaround to this problem.
It seems that the agent is still busy with the installation and during that same moment it try's to install the VSE.
Solution is to use tags and stall some time:
I created a tag install_VSE and set this to a deployment task to install the VSE.
Then I scheduled a query at night which checks on client(s) which have no VSE is installed. The query will return client(s) and will give them the tag install_VSE.
The next time on connection they will get the VSE. By this method you have and automated way to install the VSE without any issues.
Yes the system error 258 means the Windows Installer Service is busy. I've only seen it a couple of times but usually it's because of another 3rd party application installing at the same time, not the Agent. Very strange indeed.