My microphone is back. I don't know why it worked but here is how it started working again. I was searching for some kind of mixer application on N800 and didn't find any. I also found out that Maemo Recorder uses Gstreamer. So I decided to just look around what was on the device and I opened Xterminal and went around with steps like these
$ amixer
(said not found)
$ alsamixer
(said not found again)
$ cd /
$ cd dev
$ ls -l
$ cd dsptask
$ ls
$ ls -l
$ exit

And tried Skype again. And the microphone was working again!! I tried Maemo recorder again. It worked the first time. Then I exited out of Maemo Recorder and tried Maemo Recorder again. The microphone was gone again. No more microphone in Skype or Google talk or Maemo Recorder. I then tried the commands listed above again and the microphone was working again. I am not sure what happens by just going to Xterminal and browsing around but microphone comes back. So I just went and uninstalled Maemo Recorder and things are back to normal again. The microphone works in both Skype and Google talk again!! No more Maemo Recorder for me :-(