I ended up getting the Costco bag, and haven't had any trouble. It's definitely too deep, especially with the outer pockets full - but when carried like a briefcase onto the plane, I haven't had anyone stop me. I don't remember the brand offhand right now and my other half has it on a trip at the moment, but I know it wasn't the Ciao version that they used to carry. It's also not the convertible one they sometimes have in store.
Thank you for the new link, btw, I'll definitely check them out. Since moving back to Florida, we've been on Southwest a lot and don't have to worry about luggage size, but I'm still interested in having a bag that actually meets the personal item size requirements.