From what I understand, there's two different types of checks. I assume you're referring to the police checks you have to include with your application. But there's also another background security check which they do (not sure if they do it for everyone...I read on another forum that they only do it for a minority of specific cases or for applicants from certain regions), which is conducted by CSIS (http://en.wikipedia.org/wiki/Canadian_Security_Intelligence_Service). This one is handled directly by CSIS and is totally independant of CIC. Apparently they do a deep background check on the applicant and deal with every country you've lived in for more than 6 months to make sure your background checks out, and that you're not a potential security risk to Canada. The time it takes seems to really vary from case to case.