As far as I know you can store MaidSafeCoin on a BTC address but take note, the btc address where you will store it must be your own, I mean in your own is that you have complete control over the private key of the certain btc address where you will store your MaidSafeCoin. You just need to go to www.omniwallet.org when you need to send them somewhere by importing your btc address to it. You are right about storing a little BTC on the same address for the transfer fee. To answer your last question, I don't know if there are other coins that can be stored on BTC address other than MaidSafeCoin.
Thank you, so storing them on a Bitcoin Paper Wallet would be a safe bet? Also how much BTC should I also send to it?