I can confirm the same here, still 100% reproducible with
KMix Version 4 under KDE-4.8.1 (Gentoo) + pulseaudio-1.1 + dbus-1.4.18

(maybe also of interest: the opposite way works perfectly, mute/unmute via pavucontrol is reflected perfectly by the kmix applet!?)

I noticed something that might be related: Right clicking on the mixer icon in the systray and checking the box in front of "mute" ("stummgeschaltet" in german) will unmute the sound. Unchecking the checkbox, will mute it again. On the other hand, if the sound is initially unmuted, and then the box is checked, sound will be muted as expected. (So it appears that the initial state of the checkbox is wrong.)

While I am at it: This checkbox is redundant. The left-click menu has a button with the exact same meaning, below the volume slider. So the entry in the right-click menu is probably unnecessary.

I know the issue existed, but am not entirely sure about in which versions. Please try again with KDE 4.8.3, as I did changed behavior there. It works for me in both ways (muted->unmuted , unmuted->muted) and independent on whether you operate pavucontrol or KMix.
Please report back after you tried.

I upgraded to KDE-4.8.3 and it still behaves the same as I described above. But in contrast to what Dennis told, event that "check box" trick does not work, that strange check box is always disabled and never changes its state.

Some additional info: I do not use the pulseaudio backend directly (I even compiled kmix without pulseaudio support) - instead I use ALSA which then goes to pulseaudio, so the path here is: "kmix -> ALSA (high level) -> pulseaudio -> ALSA (low level) driver".

Thomas, is pulseaudio running or not?
Important: You must not mix up the two operation modi: You must operate EVERYTHING with Pulseaudio or EVERYTHING with direct ALSA. Everything else will lead to issues.

Of course pulseaudio is running and everything is fully functional: playback, recording, volume control, muting - only "unmute" via kmix does not work. 

And as I already wrote, I use ALSA for upper layer API and then pulseaudio, via this simple ~/.asoundrc:

pcm.!default {
    type pulse
}
ctl.!default {
    type pulse
}

=> For me the question is: "why such an 'asymetry' - _mute_ works but _unmute_ does not?"

some additional information, I found out that the following scenario works:

1.) make sure that sound is unmuted
2.) call "kmixctrl --save"
3.) mute the sound throught kmix => sound is muted
4.) call "kmixctrl --restore" => sound is resored (in unmuted state)

With regards to kmixctl, it should really do nothing when used on top of PA. There was a bug in kmix prior to 4.8.3 that mean it didn't detect pulseaudio. Even in 4.8.3 there was still a bug that meant things still misbehaved at times. These should be fixed now.

The fixes (in order) from git master are:
3e2b3e169f0c4ffc3a6309dbb2202fc7c2c00164   <-- included in 4.8.3
a4df93aee07fde55e3d9200d2cde0063e7b68a33
1749da9d029dc0fe42604ec9bf17d45abac74428

With these fixes applied the kmixctl should do nothing.

In my build here however, I have the 4.8.3 only (the above two fixes are not included) and I cannot reproduce the problem when working in full PulseAudio compatibility mode.

As for using the low-level ALSA controls via kmix when it's compiled with PulseAudio support, there is no reason to recompile kmix - just set KMIX_PULSEAUDIO_DISABLE=1 in the environment and you should get alsa only mode. In this mode I *CAN* reproduce the issue.

The reason it happens is somewhat complicated, but this is what happens.

You have two alsa kcontrols (maybe more) in the active pipeline: "Master" and "PCM" (this might be different on your h/w but the principle is the same). As these are both in the pipeline, both affect the level of sound heard (i.e. they are multiplied together and muting either one will result in a mute overall). When you middle click on the kmix tray icon, it mutes only the "Master" control in alsa. In the background however, Pulse notices a "change from alsa" with regards to the Master control's mute status. It detects it as being muted and then implements it's own logic to say, "if Master is muted, so should PCM be". Pulse does this because some h/w can have leakage when not all controls in the pipeline are muted (e.g. you may still have a hum that can be audible). So this is then fed back into kmix (as it also notices a change from alsa and reflects that in the GUI). So the outcome of this is that muting Master causes both Master and PCM to be muted, but unmuting Master, does not affect the mute status of PCM so Pulse still sees the sink as a whole as muted. Only when you unmute both Master and PCM in kmix does pavucontrol show the sink as a whole to be unmuted.

Now it doesn't really matter which you mute first in kmix. Transitioning either Master or PCM from unmute->mute will trigger the same reaction from Pulse - both get muted. Likewise, the order in which you unmute them in kmix also doesn't matter.

On the whole, while this is arguably annoying behaviour, I think both kmix and Pulse are behaving as intended. Therefore this bug has to be closed as invalid (it would be possible to reproduce it with "amixer -c0 set Master 0% mute; sleep 1; amixer -c0 set Master 50% unmute", thus totally excusing kmix of all blame).

Pulse itself needs to maintain control over the whole audio pipeline. It's one of it's jobs to do so. In general I'd recommend NOT looking at low level mixers values unless something is going wrong and you are debugging. PA may surprise you in how it adjusts them in normal usage. e.g. if you have the sink volume at 90%, but with only a single stream playing with it's volume set to 50%, then Pulse will NOT set the alsa kcontrols to 90% and do the further attenuation in software for the stream - that's inefficient. It will instead set the h/w to 50% and avoid any software attenuation. So if you happen to look at the underlying alsa controls when this stuff is going on, things will look pretty crazy and won't be overly useful to a user. For this reason, I'd say that if you use Pulse, you should do so wholesale. Use the PulseAudio support in kmix and live in blissful ignorance!

If you absolutely must have complete control, you can still make things work, tho' it's a lot of work. You first need to look at the PA setup for the sinks you use, take a note of the module arguments to module-alsa-sink (use "pacmd ls"). Then using pavucontrol, set the Card Profile to "Off". Then edit the default.pa and load the alsa sinks manually using broadly similar arguments to what was used via autodetection. The only difference is you should add the control=Master argument to set the kcontrol to use for volume adjustments. This means PulseAudio will no longer control the whole pipeline, but only one kcontrol. Depending on your hardware this might break Headphone handling in PA 2.0 (where the kcontrols are automatically switched when a headphone jack is inserted), so use this approach at your own risk.

Hopefully this now gives a full understanding of the issue.

All the best.