I held off getting a smartphone until 2011. But I certainly experienced this sort of discomfort without my dumb phone and various other bits of paraphernalia like a bus route map, bus schedules, a Thomas Guide map book (or AAA map once I moved to NM), lists of emergency and nonemergency contacts, medical info, todo and shopping lists, and probably a few things I'm forgetting. Most of this has been subsumed by the smartphone, in a smaller, more convenient package with better ergonomics. Battery life has improved to the point that I no longer bother with an external battery pack, unless there is overnight travel involved.
I'm pretty draconian about controlling notifications, and try to use the smartphone as a tool rather than a content consumption device (an eink ebook reader has replaced my habitual paperback book, both at home and on the go).
But as a tool, an occasion for the smartphone's absence is definitely cause for discomfort. OTOH, there are physical tools I don't bother to carry anymore (eg. a swiss army knife) that haven't been replaced with anything.