"Charmed, I'm sure"

Whence does this phatic phrase derive it's vigour? I suppose the "Charmed" part might make sense from a gentleman being introduced to a lady, but what exactly is the motivation for "I'm sure"? I would be happy with even a reference giving earliest examples of the usage -- sounds Victorian, like skirts for tables.