The nokia n800 had a little triangular stylus with a holder built into the device. So nothing extra to carry around. It also wouldn't be too tricky to attach the stylus to the device with a wire.
Stylus slots are not new. All the iPaq-like PDAs had them as well, and people still complained about losing them. I never lost mine but it was a relatively common complaint. (I still have it in fact, tucked away in a drawer in my "smartphone" from 2004[1])