Server object instance creation failed on all SOC machines is triggered when the SOC account does not have access to the resources that your trying to publish.
Try right clicking ArcCatalog and running it as the SOC account. Can you browse to \MyServer\ArcGIS Resources\Test\ and able to see the MXD, layers and toolbox?
Everything used in the model needs to be accessible to the SOC.
See preparing resources for publishing for more details on how to setup the relevant permissions.
You can't deploy this without access to the GAC libraries, which are installed as part of ArcGIS Desktop or ArcGIS Server for .NET; there is no way of deploying an ArcObjects toolkit without first installing the above.
We deployed it with all it's library files contained in the deployment. This worked, but was completely at odds with ESRI licensing.
So in short, you can't do it without AGD or AGS 10 installed.
One other thing to note, regardless, and a major difference betwen 9.3.1 and 10, is that Once your tool model runs correctly, the tool needs to registered with the ESRI component categories before it can run within an ArcGIS Server 10 instance.
We have done this registration by creating a C# .Net setup project within our base C# .NET solution. This project has changed completely as a result of differences in component category registration functionality between ArcGIS 9.3.1 and ArcGIS 10 products.
Esri recommend placing common component category registration functionality in a separate C# .NET project that produces a DLL. This common DLL is then included within each setup project that needs it.
nerdy:
In ArcGIS 9 you used to register custom components with the ESRI component categories using the Windows registry. That's all gone and you do it via the 'InvokeEsriRegAsm'. It's the ESRI way of hooking the assembly in with COM without polluting the registry
E.g. Example of what I mean : ESRIRegAsmtility
Best Answer
I think an error like yours, seen when you try to Start a Geoprocessing Service either manually or as part of Add New Service (i.e. when it is first created), is likely to be due to trying to start too many Geoprocessing Services for the resources the hardware hosting them has available.
If you Stop one or two others then you should be able to Start this one.
If you do have too many Geoprocessing Services running for your resources, and are publishing each task from a different map, then perhaps try adding multiple tool layers to just one map before you publish it as a Geoprocessing Service with multiple tasks available.
UPDATE
Just realized that you are publishing a toolbox rather than a map with tool layers so much of what I said above may not apply. However, if this toolbox does not publish then maybe a smaller one with less tools might? If that's the case it would still point at system resources being limiting.
UPDATE 2
It seems like the error message I looked up and "matched" to this question is not quite the same.
I now think that attention should be paid to the "Invalid parameter" part of the Question's error message. I think you should double-check that the tool can be run from ArcGIS Desktop on the server where you are trying to run it as a GPservice. I would expect that would throw a similar error and enable you to focus on debugging the model and dialog rather than the service.