I checked over everything, and as the last attempt I tried running osu! with administrator privileges. To my surprise, the problem was fixed. However, I'm still confused as to:
1) Why did this happen in the first place? Yea I moved the songs folder, but there this problem appeared a month after that.
2) Why I checked over and applied read and write access to all folders to all users and groups and the problem still persisted.
3) I saw no difference in the folder and file settings among maps that worked and maps that didn't. So why did some work and some did not?
And sorry for having you to spend time figuring out this problem to which you mentioned a possible cause already. Well if we learned anything with this, it is the above and that osu! seems to handle the lack of permissions weirdly. Thanks for the help.