1) Regarding the N of M approach that you mention, is the easiest way just to have say five sheets, each with a fifth of the code sequence/keys that shows up on the paper backup or is there a better way.
The newest Armory has an N of M paper backup. If you make a 3 of 5 backup, then you print five sheets of paper, each with a code on it. You can restore the wallet from any three of these. If a thief gets two of them, he has no information at all about the wallet. If you lose one or two of them (fire?), then you can still recover your funds, as long as you have three pieces left.
It is using Shamir Secret Sharing,
http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing2) Also, any recommendations/resources for creating bomb-proof, yet easy to remember pass phrases.
Any passphrase that is easy to remember will be insecure. Any passphrase that is secure will be forgotten
Seriously, you could use a sentence that is partly nonsense but still meaningful to you. Or a sentence that is meaningful to you, but only use the first three letters of each word.