The official way is to have the start code prefixes present (which are necessary for having multiple NAL units in one packet) - this is what all OpenMAX IL (the standard used internally below MediaCodec) decoders expect (even if some also may support other formats). Whether you have SPS/PPS in a separate buffer (with the BUFFER_FLAG_CODEC_CONFIG
flag set) or prepended to a buffer with VCL NAL units shouldn't matter - decoders should be able to handle both I think. I don't think you'll find any individual document that clarifies this for Android though, other than implicitly deducing it from what devices actually do.
Can you name which devices (and which platform versions) output which combination of these bitstream variants, and which combination fails on which device? AFAIK a stream with startcodes present should work everywhere, but there may of course be exceptions. Since Android 4.3, these things should be much more well-behaved than they were on 4.1 and 4.2.
Some vendors do seem to do nonstandard things in MediaExtractor - I've written a bug report about this at https://code.google.com/p/android/issues/detail?id=74356. In that case, the Samsung specific nonstandard behaviour is signaled with a isDMCMMExtractor=1
key in the MediaFormat. I really agree that MediaExtractor should be stricter specified, because right now it's mostly only usable for feeding data into MediaCodec (where it is assumed to be understood, at least for the vendor specific HW codecs), but it's hard to say what it actually does, if an app would want to do something else with the MediaExtractor output (e.g. decode with a third party bundled decoder, or send the extracted data over the network, etc).
If some device fails to decode the de-facto standard bitstream format (but only succeeds if it is mangled the way that platform's MediaExtractor does it), it sounds like another CTS compatibility test is warranted, by testing decoding of raw, hardcoded packets (so that MediaExtractor can't get inbetween and transform things). Do CTS tests like EncodeDecodeTest (see http://bigflake.com/mediacodec/) work properly on this device? If it does, but if decoding standard packet formats fail, it would mean that the device's encoder also outputs something nonstandard.