So what is the recommended transaction fee to input manually to guarantee this does not happen? This is making me scared to make transactions now.
Most wallets will calculate the proper fee for you. What wallet are you using that you have to enter it manually?
The OP probably either had a setting wrong on QT or made a typo when creating a custom transaction on blockchain.info. I have accidentally paid .001 instead of an .0001 fee a couple of times using custom send :/