About the lenght of the private key (making sure your key can fit under a sticker), have you tought about using a private key in mini private key format?
https://en.bitcoin.it/wiki/Mini_private_key_formatAs for your other problem (the durability), i guess it completely depends on your choice of materials. If you use high quality paper, good ink, laminate your wallet and store it in a safe (dry, no light, no changes in humidity) i guess it can last a long, long time...
You can also etch keys in metal, or wood,... I guess you're only limited by your imagination.