I could see using one of those army "dog tags".
As long as you can find someone who will use mixed case... or possible find a vanity address generator that can enforce all caps?
I just came across
brainwallet.org.
It has a convert tool that can output a key in RFC1751 format.
This is all upper case like this,
5JbrP892xZEXW9ZAyxaspYYW1qUYk4epi1E5qrVuyo18LET7Zgv equals
CLAW LOOT QUO FANG BLED GEL GWEN BIND OFF
CLOD REST HUNK SAM BOSE DUET ARMY KIT OK
MOOT SOUL LUND TIDE BOUT KLAN
Unfortunately it's 112 chars and according to the dog tag offer they can do 5x15 = 75 char only.
So two tags would be needed, as offered for $4.99. Which isn't a bad idea anyway. Keep them in two places and bring them together when needed.
Or use hex - but upper case, only 64 chars =>
67764CD7BEE5902
D91CB04BAB3DCE
F393A4BADDFA722
245EBEDC5AD0f59
5DD4E