I've never lost the first scenario yet - I've played with Agnes 2 times (solo) and Roland once.
I admit that I've had some fortunate draws with Agnes though, often getting exactly what I need when I need it, but I do make sure to draw a lot of cards to help speed her up to get the cards I need.
One of the 2 times, I did not play with her recommended starter deck. I took out some of the cards I didn't like for her (removed knives, and a couple specialty cards that I wasn't using much) and replaced them with more neutral skill cards to help her draw the cards she wanted most even faster. Besides the knives, I did not remove many though. It did make her even more risky though as she has so few +damage assets.
Edited by xuzuthor