I recently did this with an asynch GP service for a WPF xbap client app, but the same approach should work with flex too, assuming flex has something equivalent to Json.NET.
The GP service took a single string as an argument, a serialized data transfer object (DTO). I found it easier to change the DTO fields as requirements evolved instead of adding args to the gp service. The DTO was a complex object that included basically a description of how the layout should look with map element that contained a collection of layers, text elements, legends etc. Layout description templates were presented to the a user from a different REST WCF (non Esri) web service. The GP service would create an mxd from the DTO save it on the server, then export it to a pdf (as well as a low res jpg preview). Saving the mxd made it easier to troubleshoot issues.
There was a slow memory leak somewhere in the pdf exporter that I fixed by simply setting the gp service to be non-pooled. I set the messages to report progress back to the client. I think that would be a lot more complicated with an SOE. I did also use an SOE, though, for culling the legend (removing symbols that do not fall within current extent).