Congratulations on your new daughter!
1. My wife needs many police checks which will take months. Should we submit the application before we have the police checks or wait for a complete application first?
Start the police checks right away, even while mulling over when to submit the application. If you are at the point you have EVERYTHING except your police checks, then you can make that decision. At the present time it is taking 2 months to obtain sponsor approval. Sydney (which processes outland applications for NZ) is listing the 80% time as seven months
to confirm this, and follow the Sydney link to note that they process NZ applications.)
A well-prepared application is likely to take half that time (3.5 months) - this is probably closer to the 50% figure, which is usually a better guide for an application without issues. If the application shows up without the police records and they aren't there yet, add at least 2-3 months to that time (putting you in line with the 80% figure.) Once you have the police clearance letters, you should forward them to Sydney (assuming you have a file number. If you don't, you should wait until you have one. CIC is really good at losing things.)
I prefer to submit a complete application, as it means you're likely to have short processing time once it does hit the visa office. But others have done well submitting in advance and then following with police certificates.
2. For someone like me who there shouldn't be any question about genuine relationship etc is it still preferable to apply outside rather than inside?
Inland: 11 months to open the application + 8 months to process it = 19 months. You get the open work permit after the 11 months.
Outland: 2 months to open the application + 7 months to process it = 9 months. You (or rather your spouse) get to work when PR is granted.
So, in the time you can complete PR via outland you will still be 2 months short of inland AIP.
The one advantage to inland: you don't have to demonstrate the credible plan for returning to Canada, since you'll already be in Canada. Your wife shouldn't have any issues entering (coming from a visa exempt country) but the border officer might give her grief (since it is obvious that she doesn't really intend for the visit to be temporary.) Of course, you could plan on a scouting expedition ("visiting to plan a return back to BC") and then change your mind (plans do change).
3. If we apply outside and I am approved as a sponsor can my wife receive an open work permit, enter Canada and wait for the decision? Or can we just rock up and do an inland application and apply for an open work permit?
She cannot obtain an open work permit via outland sponsorship. She would receive one via an inland application. However, as is often observed, the complete processing time for outland is less than just the first stage for inland - so she still ends up with the ability to work sooner than via inland.