I saw someone on an engadget post mention that they purchased this case so I figured I'd pick one up and give it a shot. The case fits the N800 perfectly in the bottom half with the elastic band. If you put the N800 in it's original soft pouch that shipped with the unit you can still place it in the Case Logic case and secure it with the elastic strap. I put my headset in the mesh pocket on the top half and it all fits great!

Yes, it's a little bulky but it's a very sturdy hard case. It's available on staples.com for $19.99 but I picked mine up at a local Staples store for $14.99. Here's a link to the actual Case Logic page:

http://tinyurl.com/2ewznr

EDIT: Added links to pics with N800 inside
Pic 1
Pic 2

I've seen those and wondered if it would be a good fit. You're right, it's bulky, but the extra protection seems worth it. Thanks for the post.