The techniques mentioned (personas, card-sorting, etc) are all well known "best practices" in user experience design. The large successful companies in the consumer space (Amazon, EBay, Expedia, etc) adopt these practices (or derive their own mix based on these).
Do startups use these? Some do, some don't. Depends on the time frame, the resources available, and the knowledge and skills of founders.
This is similar to software development methodologies (agile, TDD, XP, etc). Some coders at startups are aware of these software development methodologies and follow them diligently. Others follow their own loose interpretation of these.
Some startups are successful purely with the blind, gut-feel approach: one smart programmer writing code with no methodology, plus one talented UI designer likewise working intuitively without the detailed upfront work. Of course, many startups fail, or have severe growing pains (Twitter for example).
Methodology and process, whether in coding or in UI, helps reduce the risk and insure successful outcome. You can still fail, and many do. Also many teams (especially in older, stagnant organizations), follow these processes blindly, as empty rituals. Ceremony does not guarantee success.