[Galaxy S III I9305 (4G LTE + 2GB RAM) Android Deve] FruitieX:
Ok, I narrowed down the issue to being Google Now's fault... Any time Google Now would start listening for voice commands (*INCLUDING* the "OK Google" command at the KitKat homescreen!) it'd change a bunch of volume settings, presumably to mute any playing media, but it doesn't seem like it restores the settings properly.

Here's a snippet of a logcat when starting Google Now's voice recognition function:

I/MediaFocusControl( 2590): AudioFocus requestAudioFocus() from android.media.AudioManager@64ba9cf8com.google.android.voicesearch.audio.AudioRouterImpl$1@64c52780
V/MediaFocusControl( 2590): updating focussed RCC change to RCD: CallingPackageName:com.google.android.music isFocussed:true isAvailable:true
V/LocalDevicePlayback(30550): AudioFocus: received AUDIOFOCUS_LOSS_TRANSIENT
I/LocalDevicePlayback(30550): pause: transient=true, currentPos=4
I/Icing.InternalIcingCorporaProvider( 6303): Updating corpora: A: NONE, C: DELTA
D/LocalDevicePlayback(30550): Event logging MUSIC_PAUSE_PLAYBACK_REQUESTED: [4136, DEFAULT]/0502ebc8-87ec-31ad-974e-e0a7860331b0
W/art ( 6303): Thread[53,tid=2228,Native,Thread*=0x44a03b00,peer=0x6514a8f8,"Thread-1536"] attached without supplying a name
D/audio_hw_primary( 1980): select_input_device: AUDIO_DEVICE_IN_BUILTIN_MIC
V/audio_hw_primary( 1980): Changing output device 8 => 8
V/audio_hw_primary( 1980): Changing input device 0 => 4
V/audio_hw_primary( 1980): Set 'HP Switch'.0 to 1
V/audio_hw_primary( 1980): Set 'Headphone Volume'.0 to 50
V/audio_hw_primary( 1980): Set 'Headphone Volume'.1 to 50
V/audio_hw_primary( 1980): Set 'Headphone ZC Switch'.0 to 0
V/audio_hw_primary( 1980): Set 'Headphone ZC Switch'.1 to 0
V/audio_hw_primary( 1980): Set 'AIF1DAC1 Volume'.0 to 96
V/audio_hw_primary( 1980): Set 'AIF1DAC1 Volume'.1 to 96
V/audio_hw_primary( 1980): Set 'AIF1 Boost Volume'.0 to 0
V/audio_hw_primary( 1980): Set 'DAC1 Volume'.0 to 96
V/audio_hw_primary( 1980): Set 'DAC1 Volume'.1 to 96
V/audio_hw_primary( 1980): Set 'Left Output Mixer DAC Volume'.0 to 7
V/audio_hw_primary( 1980): Set 'Right Output Mixer DAC Volume'.0 to 7
V/audio_hw_primary( 1980): Set 'AIF1DAC1 EQ Switch'.0 to 1
V/audio_hw_primary( 1980): Set 'AIF1DAC1 EQ1 Volume'.0 to 16
V/audio_hw_primary( 1980): Set 'AIF1DAC1 EQ2 Volume'.0 to 14
V/audio_hw_primary( 1980): Set 'AIF1DAC1 EQ3 Volume'.0 to 12
V/audio_hw_primary( 1980): Set 'AIF1DAC1 EQ4 Volume'.0 to 14
V/audio_hw_primary( 1980): Set 'AIF1DAC1 EQ5 Volume'.0 to 16
V/audio_hw_primary( 1980): Set 'Main Mic Switch'.0 to 1
V/audio_hw_primary( 1980): Set 'IN2L Volume'.0 to 28
V/audio_hw_primary( 1980): Set 'MIXINL IN2L Switch'.0 to 1
V/audio_hw_primary( 1980): Set 'MIXINL IN2L Volume'.0 to 1
V/audio_hw_primary( 1980): Set 'AIF1ADCL Source'.0 to 0
V/audio_hw_primary( 1980): Set 'AIF1ADC1 HPF Mode'.0 to 0
V/audio_hw_primary( 1980): Set 'AIF1ADC1 HPF Switch'.0 to 1
V/audio_hw_primary( 1980): Set 'AIF1ADC1 HPF Switch'.1 to 1
V/audio_hw_primary( 1980): Set 'AIF1ADC1 Volume'.0 to 96
V/audio_hw_primary( 1980): Set 'AIF1ADC1 Volume'.1 to 96
V/audio_hw_primary( 1980): get_next_buffer: read_buf 0x419af740 extended to 4096 bytes
W/art ( 6303): Thread[52,tid=2230,Native,Thread*=0x47b71fa0,peer=0x65147f40,"Thread-1539"] attached without supplying a name
D/AlarmManagerService( 2590): Kernel timezone updated to -120 minutes west of GMT
D/AT_Distributor( 2241): gUartPath = /dev/ttySAC2
D/AT_Distributor( 2241): UART ttySAC2 is used by console
E/AT_Distributor( 2241): Failed to init ATD
D/MobileDataStateTracker( 2590): default: Broadcast received: android.intent.action.ANY_DATA_STATE apnType=default
D/MobileDataStateTracker( 2590): default: Received state=CONNECTED, old=CONNECTED, reason=(unspecified)
D/lights ( 2590): set_light_buttons: 2
I/AudioRouter( 6303): ROUTE_NO_BLUETOOTH->ROUTE_NONE

And here's the continuation of that log when the Google Now voice command times out (continues right where the previous one ends, just separated for clarity)

I/MediaFocusControl( 2590): AudioFocus abandonAudioFocus() from android.media.AudioManager@64ba9cf8com.google.android.voicesearch.audio.AudioRouterImpl$1@64c52780
V/LocalDevicePlayback(30550): AudioFocus: received AUDIOFOCUS_GAIN
V/MediaFocusControl( 2590): updating focussed RCC change to RCD: CallingPackageName:com.google.android.music isFocussed:true isAvailable:true
I/MicrophoneInputStream( 6303): mic_close
D/lights ( 2590): set_light_buttons: 1
V/audio_hw_primary( 1980): Changing output device 8 => 8
V/audio_hw_primary( 1980): Changing input device 4 => 0
V/audio_hw_primary( 1980): Set 'HP Switch'.0 to 0
V/audio_hw_primary( 1980): Set 'AIF1DAC1 EQ Switch'.0 to 0
V/audio_hw_primary( 1980): Set 'Main Mic Switch'.0 to 0
V/audio_hw_primary( 1980): Set 'MIXINL IN2L Switch'.0 to 0
V/audio_hw_primary( 1980): Set 'MIXINL IN2L Volume'.0 to 0
V/audio_hw_primary( 1980): Set 'IN2L Volume'.0 to 10
D/audio_hw_primary( 1980): select_output_device: AUDIO_DEVICE_OUT_WIRED_HEADPHONE
W/art ( 6303): Native thread exiting without having called DetachCurrentThread (maybe it's going to use a pthread_key_create destructor?): Thread[52,tid=2230,Native,Thread*=0x47b71fa0,peer=0x65147f40,"Thread-1539"]
W/art ( 6303): Native thread exiting without having called DetachCurrentThread (maybe it's going to use a pthread_key_create destructor?): Thread[53,tid=2228,Native,Thread*=0x44a03b00,peer=0x6514a8f8,"Thread-1536"]
D/AT_Distributor( 2247): gUartPath = /dev/ttySAC2
D/AT_Distributor( 2247): UART ttySAC2 is used by console

Notice how it doesn't seem to restore the value of e.g. "Headphone ZC Switch" and a bunch of other channels. This may be what is causing problems?

As a quick workaround for anyone else experiencing this issue: Disable the 'Hotword detection' setting in your homescreen settings -> Voice, and avoid using Google Now voice commands when using headphones.

ps. Yes I'm using ART, but testing this with Dalvik gives the exact same results.