I know this is an old question, but I would just like to share the solution we found for the problem we had in case others encounter it.
In our case, we were testing with a SSRS server that did not have HTTPS enabled. We were calling the method "LoadReportAsync" from ReportExecution2005.asmx, passing a "new ReportExecutionTrustedUserHeader()" instance in the first parameter.
Apparently, with a newer window server version (or something else newer, i don't know for sure) this can only work if you call an HTTPS website.
If you call an HTTP website, you need to pass "null" instead.
This was not an issue on an older server. This is not an issue with ReportService2010.asmx (we can pass a trusted header without getting an OperationNotSupportedNativeModeException).
I would like to give credit and thank BJ Safdie whose answer pointed me in the right direction here : https://stackoverflow.com/questions/10922645/ssrs-2008-execution-service-loadreport-error
Not sure that it will help in all cases, but hope it will be useful to someone else too.