Appreciate the reply guys. Hey Tim, I don't think it's the cache. Have tried it numerous times.
I tried your suggestion Brenden. I do have extensionless URLs and when I used 404.aspx instead of 404, it didn't display the right page. Also, 404 is a document/page I just created and not a physical aspx file on my root.
Should I use physical aspx files as the page not found url?