After sometime with no Skyrim I had some play today thinking of making some progress on A Daedra's Best Friend quest.
The objective led me to the shrine, and it was indicating that I'd already retrieved the Rueful Axe, but as I went and told to Clavicus, he was talking like I had options whether to keep the axe and kill Barbas or give it to Clavicus. But the conversation option appeared there was only "I think I want to keep the axe", where I don't want to do that and I just want to give it to him.

I opened my inventory to figure out how I could give it to him, then I found out that I didn't have the Rueful Axe in my inventory!
I've tried loading a little bit earlier saved data to see if I had it before the talk with Clavicus, but it wasn't in the inventory at that time as well.

I tried going to the cave where the axe had been supposed to be (the cave was marked as cleared though), in an attempt to retrieve it again, but the axe wasn't there, and a sight inside the cave reminded me that I'd actually been to that cave before. I thought maybe I had left it in some weapon storage of my place or gave it to my companion, thinking it should be weird because as I know quest items cannot be removed from the inventory, and after all I couldn't find it in anywhere.

I really don't know what's going on here...
Maybe I did something on the axe and I don't remember it since I didn't play Skyrim for a while. But it should be weird and it must be in my inventory no matter what because it can't be removed.
Or is it a bug that at some point the axe was removed for some reason?

I have no clue on this... anyone any idea?
I'm playing on Xbox 360.

Ouch. Unfortunately, it seems like you have exhausted many of the possibilities. The only thing I could suggest at this point would be to reload a save before you started the quest. Best of luck!