Did Gollum deserve death?

[The Might]

As Mithalwen already pointed out, Gollum never was on an errand for Sauron intentionately.
This matter is presented well in the Hunt for the Ring chapter of the UT.
It is said that after Gollum was allowed to escape, he was followed by spies from Mordor, but that they were unable to follow him in the Dead Marshes. Afterwards he was captured by Aragorn, and taken north to Thranduil's realm.
If he had known that by seeking The Shire he would help Sauron find the Ring, he would have definitely taken much more precaution. Gollum definitely hated Sauron, and saw him as his greatest foe, if it was someone Gollum would have done anything to prevent from getting the Ring, it would have been Sauron.

One could debate that he might deserve death for other deeds such as killing Deagol, but definitely not for serving an evil power.

[Macalaure]

Originally Posted by Mansun

In the real world Gollum would be put to death.

I'd say this depends largely on the 'where' in the real world.

Concerning whether servants of Sauron deserve death or substantial punishment:

'You think, as is your wont, my lord, of Gondor only,' said Gandalf. 'Yet there are other men and other lives, and time still to be. And for me, I pity even his slaves.'
~The Siege of Gondor

I think it is one of the key elements of the LotR, that even though one might indeed deserve death, he should still be pitied, if this is possible.

[Raynor]

Originally Posted by Macalaure

I'd say this depends largely on the 'where' in the real world.

I agree. I fail to see how dealing out death would redress any past deeds. I also believe that Manwe's words concerning justice/healing in the case of Finwe and Miriel can apply in here too:

Originally Posted by Of the severance of marriage, Manuscript A, Later Quenta Silmarillion, HoME X

Neither must ye forget that in Arda Marred Justice is not Healing. Healing cometh only by suffering and patience, and maketh no demand, not even for Justice. Justice worketh only within the bonds of things as they are, accepting the marring of Arda, and therefore though Justice is itself good and desireth no further evil, it can but perpetuate the evil that was, and doth not prevent it from the bearing of fruit in sorrow.