Reviewed the project plan for a redesign I'm working on which was put together by a project manager and not informed by a UX'er. The project plan asks for the site map deliverable to be documented first before wireframes. I just wondered if this is actually the case...in the past I've always had a high-level sitemap before I begin wire framing and then after wireframing I create a detailed sitemap? At which point should your site map be worked out?
Organizations are so hung up on deliverables that it turns a proper UX process into a deliverable process instead.
Which is bad UX.
The ideal is to educate the organization that UX isn't a step in the process with a set of defined deliverables, but rather it is part of the process itself, and the deliverables will change from project to project and even on a defined project, the deliverables will be living documents, not set-in-stone signed-off milestones.
UX is all about guiding the process rather than adding another layer of documentation.
To answer your specific question:
The answer is, unfortunately: it depends.
In some cases, it's not worked out until after the first release and user feedback starts coming in.
It's a reality of the Internet that the sitemap for any given site is never "fully worked out"; websites need to be designed from the get-go to be scalable and to adapt to change, especially since most sites nowadays are driven by a CMS that allows people to add new articles and even pages as necessary.
For me the information architecture (IA) is designed as one of the first things after requirements (including personas) are established, since they help provide a skeleton upon which to hang things like wireframes and content inventory from.
It's important, though, to be willing to adjust the IA as requirements change, and to design it from the get-go to be adaptable to new pages being added. Sometimes that means your card sort (or whatever equivalent activity you perform) may not use the exact naming you use on the final website.
I would speak to your Project Manager and explain that the sitemap is a living document as stated above by DA01.
Site maps change constantly and never sit still, even during the development stage the site map can change, UX is about testing and refining so quite how they expect you to product a sitemap before hand is baffling.
A PM is all about deliverables which is where the arguments usually stem from, try to reason with them, if this doesn't work try and relate it to their job role. Ask them to provide a list of deadline dates that will not change at all throughout the whole design & development process. When they turn round and say, "hmmm things change so they the dates may change over time" simply reply with "exactly"
Saying that, there is nothing wrong with creating a high level sitemap at the start of a project, personally I will create a rough sketch of the sitemap as this allows me a basis to work from, I know the key components of whats to be contained within the app; homepage, contact, downloads, blog. I just build onto these as I go through.