This solves the problem. When "Plex Media Server.exe" runs another executable, the attempt is intercepted, and the command line is changed, as described by enachemc on the Plex forum. The command line change tells the transcoder that the device can accept H.264 video at up high profile, 1080p, and level 4.1.
The interception is done using Detours from Microsoft Research. I chose Detours 2.1 because I had problems with Detours 3.0. The code is compiled from PlexTranscodeDetour.c, creating PlexTranscodeDetour.dll. That DLL needs to be inserted into the "Plex Media Server.exe" process. I recommend insertion via withdll-silent.exe. It supports the same switches as the ordinary Detours withdll.exe, but doesn't open a console window. For example, if Plex Media Server is installed in "C:\Program Files\Plex\Plex Media Server" and these files are in "C:\Program Files\Plex\PlexTranscodeDetour", then you can change the Plex Media Server shortcut target to:
"C:\Program Files\Plex\PlexTranscodeDetour\withdll-silent.exe" "/d:C:\Program Files\Plex\PlexTranscodeDetour\PlexTranscodeDetour.dll" "C:\Program Files\Plex\Plex Media Server\Plex Media Server.exe"
I am also including an unmodified withdll.exe, which produces diagnostic output to the console. You only need to try that if you have problems. Alternatively, you could maybe edit "Plex Media Server.exe" to include the DLL via setdll.exe. I don't know if that works.
I recommend using Microsoft compilers such as Visual C++ from Visual Studio Express 2010. Detours does not come with binaries, and if you want to compile it, you must use a Microsoft compiler. You can't even statically link with detours.lib from the GNU toolchain because the linker cannot resolve some of the symbols in detours.lib. If you want to use the GNU toolchain, you can use the instructions I posted earlier to create a detours.dll that you can use. I felt forced to use Visual Studio Express because I didn't think I was allowed to distribute the detours.dll that I created using those instructions.
You can download PlexTranscodeDetour from Dropbox. You are free to do whatever you want with my code here. Detours components are distributed according to the license from Microsoft Research. This code and program comes with absolutely no warranty. Use at your own risk.