You know what, I love the little red icon too.
When you had the "show taskbar notifications" option on Media Center's settings ticked, did you click "Save" after it???
You can also click the arrow on the side tray and Customize, it should show you a list of the notification icons that recently appeared and if you see the red recording icon from there, just make set it to "Show Icons and Notifications" and OK so it shows everytime. Just to be clear, this "Show Icons and Notifications" I am saying is not the one on Media Center's settings...
Try scheduling a recording again, and whilst its recording, click the arrow on the taskbar and look at the square if it shows the red icon. If it does, you can simply drag it towards the side tray and that will show it everytime when its active.
If those did not work, you may consider setting up Media Center again of maybe this is a registry error.