This proves that the problem isn’t core:
I switched the theme to twentyeleven where the problem does not appear at all.
Core functions are not throwing those notices. Your Theme is calling the deprecated function(s) somewhere – perhaps in a filer callback for the_title.
Search your Theme files to find the culprit. Start in functions.php.
p.s. what Theme are you using?