Am I missing a way to unmute them?

You need to restart the game to re-enable the sounds after disabling the addon, see https://wow.gamepedia.com/API_MuteSoundFile

I did. Now after duplicating the game folder and deleting cache,wtf,interface all the walking sounds are gone for all characters even new ones when there is no addon folder. It seems like the sounds are saved on blizzard server and then affect the game even if you have no addons. I m puzzled

Do you still hear combat sounds? That would be easier to test than footstep sounds

Otherwise if you do believe that sound files are somehow loaded from the blizzard server, you can try edit this line to the following and load the addon again
https://github.com/ketho-wow/MuteAnnoying/blob/master/MuteAnnoying.lua#L45

			if not unmute[fdid] then
-				MuteSoundFile(fdid)
+				UnmuteSoundFile(fdid)
			end

Issue fixed now thanks