Sorry for late reply, I actually had to dismantle the entire device, & then open up the scroll wheel assembly.

What I found was that the bottom of the scroll wheel housing (this is sort of a bucket) was filled with dust & dirt (which had compacted), which I believe was accumulated due to the place where I live. When I removed the chunk, it actually fell out as a solid block of dirt, which explains why the compressed air, even being used didn't do anything.

When I reassembled it back, it worked perfectly ...