Ok, thanks for great advice and encouragement! Got myself a seal puller (took two visits to local Autozone until I came across the guy who actually knew what it was

) and got the old seals out today

. To my surprise it turned out that the outer metal shells of the old seals got a T-shape lip on them. Thus all the crud that scared me and which I spent several hours removing was actually on the outer side of the seals - what a shame!

What set me off though was the fact that the new seals I got from Advance Auto, while being the right size, did not have the said lip. Now I finally understand that this lip may in fact provide extra protection for the seal bore against rust. Ordered new set of seals with the lip from Rock Auto:
http://www.rockauto.com/en/moreinfo.php ... 25&jsn=381(sorry, it was the last set

)
Thanks again!
Alex