Ok, this is what happens.
With Bandit:
You steal, if there are not items to steal the game tells you and you're done. Further stealing is done at your own embarrassment. With Bandit, Steal skips gauging Spirit and checking if the Steal "hit" and goes to the stealing.
You try to steal from the Rare slot, you have a 0.4% chance to get the item.
If it's successful and there is an item you get the item, if the steal is successful but the slot is empty the game tells you the steal failed and you're done, if the steal is unsuccessful you move to the Semi-Rare slot. Repeat this for each slot until you get to the common slot (Semi-Rare has 6.25%, Uncommon has 25%, Common has 100% chance for success). If the steal is unsuccessful from the first 3 slots, and then you try to steal from the empty Common slot the game will tell you the steal failed.
Honestly, I've only ever seen the game give a steal failed message before stealing from the Common slot once.
With Bandit and Master Thief:
You steal, check for items. The game checks if the Rare slot has an item, if so you try to steal from it, with a 12.5% chance of success, if not it moves to the next slot without trying to steal from the Rare slot. If it is successful you get the item, if it fails you move to the next slot. Repeat this until you reach the common slot (Semi-Rare has a 12.5%, the others are the same for success). If you fail to steal from all of the slots that you tried to steal from you will get a steal failed message.
So to answer the question about 100% stealing, this is only the case for the Common slot. Lets say an enemy has an item in the Rare, Semi-Rare and Common slot. With Bandit, you could potentially steal from the Uncommon slot, which would result in a steal failed. However, with both abilities equipped, you won't try to steal from the Uncommon slot, and if the first 2 failed it will skip to the Common slot with a 100% chance to steal. However, after you steal that one and you try to steal again, the game will only try to steal from the first 2 slot. Each slot only has a 12.5% chance of success, so it's very possible for both of those to fail, resulting in a steal failed.