Okay so I loaded up my old level 21 saved game after a few months of not playing, check the map and I notice I had previously placed a random blue marker in the middle of no-where. So I fast-travel to Haynote Cave, travel northwards on Horseback to find a shrine, and no 'You have found 'location x'' notification, so I looked the location up in my Oblivion guide and saw no such shrine.

This is highly peculiar, I don't know iff I'm missing something completely obvious or what, the shrine has 3 followers, benches a lectern and all the normal stuff a shrine has, but no name. I found the random daedric shrine north-north east of Haynote cave in the Great forest.

Also another weird thing occured, I was just chillin' in the Imperial Bridge Inn and struck up conversation with the Imperial Guard there, he proceeded to say 'I've seen people like you, murdering b*******' etc. I went to my stats page to see that I havent even murdered anyone (I was playing on a new account). My game has had history of being incredibly glitchy, I've had it since 2006.

That one's part of a DLC.

Have you got Knights of the Nine installed?

Alois hammer beat me to it. ^_^

Ah yes, that would be it, I was doing the Knights of the Nine quests before I decided to have a break.