I'll second Meemo's recommendation for Waterfield bags at
www.sfbags.com. I have a small VertiGo on order, along with a sleeve case for my Samsung NC10 netbook. According to their customer service, the small VertiGo will just fit the NC10 in a sleeve, the power cord, and the Kindle2 in their custom sleeve.
Their site lists the Medium VertiGo as the smallest one in their bag/sleeve combo package, but I emailed customer service and they confirmed the small should be just what I need. I'll know for sure when it arrives tomorrow.
Just a note: try to use that EEE keyboard in person before you order it. 2 coworkers have the EEE 1000, and the keyboard is tiny, I even have small hands and it's hard for me to use. I much prefer the full keyboard of my NC10.