"...75 years old toilet paper on the sea bottom."
....mmm....that have to be some pretty tough toilet paper... no way it could...but wait!

Lets turn the other cheek so to speak.
"My Experience With Her Majesty's Ministry Of Supply Toilet Paper" (I have a feeling that many of our Englander cousins across the pond can relate to this story) it goes something like this.
No Sh#t there I was, a young American airman at RAF Sculthorpe for exercise Flintlock 82, in this WWII hangar. Ah, in the mens room specifically, ya know sittin down in a stall sending a message to higher headquarters. Well paperwork time came and I reached over for the TP, it was like thin wax paper, the horror (

thinks how's this gonna work

) and started laughing, sort of. Stenciled on each and every 1 ply square was "HM Government Property". To this day I wished I'd have liberated that roll as a souvenir. End of story.
Turns out this stuff was tough, used from the 1930's to 1989, especially during the UK's time of postwar Austerity, in public facilities, government offices, schools and wasn't very popular with the Brits either. Many users had their own stenciled rolls. Being the diligent Tigharian researcher I've provided some links:
IZAL Toilet Paper
http://www.dooyoo.co.uk/household-products/izal-toilet-paper/422529/Click on the 18 reviews some of which are quite humorous such as:
"Best paper in the world provided you know how to use it. Rather than dabbing and mopping with it as you would with conventional "Nancy boy" soft paper you need to do a bit of origami and form it into a small shovel and scoop away at your bum until it is sparkly clean and because of the medicated magic of Izal totally free of all known germs."

Gotta love the English way with words "bit of origami" "form it into a small shovel"
Lavatory Paper History & Stencils
http://www.ephemera-society.org.uk/articles/cloacopapyrology.htmlMy favorite TP square stencil ""Edinburgh Cleansing Department", posh, very posh.
WWII propaganda stencil-Hitler "Now I'm brownshirt all over".
TP Sheets inscribed by manufacturers or institutions.
http://bookhistory.blogspot.com/2008/02/collectanea-cloacopapyrologica-1.htmlManufactures List & Suppliers
http://bookhistory.blogspot.com/2005/12/cloacopapyrology.html
The manufactures list might be a crucial resource when
we find a screen capture of the toilet paper rolls in the 2010 ROV video.

Just think folks, we could have a whole CORAL ENCRUSTED DEBRIS FIELD OF TOILET PAPER down there!

There could be rolls stenciled Gallagher, SS Norwich City (probably all burnt in the fire), PISS, NZ Survey.
Martin this is going to take some serious research, we might need a new thread or at the very least transfer this to Artifact Analysis: FAQ Fecal Material & Coprolite.
LETS ROLL!
Rob