Both of my S4 have the Voice Recorder app. One was updated via OTA. The other was updated via Kies. As such, I would suggest you consider download and install the available original images on XDA. Good luck.
Mine never lost it; the update came along yesterday and everything seems to work OK. Is there something else going on with this (i.e., different firmware, etc.) that would cause the problem for some and not others?