OK, first we need to cover what makes a good password:
"Good" passwords are of substantial length and have the ability (often a requirement) to utilize special characters.
Why does the possible addition of special characters matter? By having more possible characters you have created a substantially larger set of combinations for each password.
Passwords need to be 8 characters using lowercase letters.
There are 26 possible characters for each position, so 26^8 = 208827064576 possible combinations.
Passwords need to be 8 characters. Passwords may include uppercase, lowercase, numerals, and special characters.
26 lowercase + 26 uppercase + 10 numerals + 30(ish) various special characters = 92 possibilities for each character.
92^8 = 5.13E15 possible combinations!
So, we can see that by increasing the possible values for each character, we have substantially increased the power required to brute force these passwords.
Why does this matter here?
Simply put, longer passwords are harder for people to remember. As a result, people are more prone to write passwords down as well as reuse them. Therefore, in answer to your first question: No, you will still need to change passwords.
People may report when they lose a company laptop, but may not tell the company if their wallet was stolen (with passwords written inside) or that their Yahoo account was hacked (which conveniently used the same password... but of course the company doesn't know this.)
In regards to your second question...
It depends, key loggers aside:
Let's assume the laptops have password encrypted drives.
If the laptop is turned off when stolen. you're fairly safe.
If the laptop is on, you're in trouble - regardless of whether the machine is logged in or not. A couple quick examples:
-Programs such as Cain & Abel could dump any passwords stored in browsers or on the local machine.
-Additionally, some machines with firewire could be susceptible to Direct Memory Access attacks which can leak contents of the memory. (Lucky for hackers, some firewire cards are Plug-and-Play!)
If the laptop is in sleep mode, the RAM retains just enough power to keep the memory contents alive. So any recently used passwords could theoretically be gleaned by "those with the knowledge of these things". (E.g. liquid nitrogen bath to the RAM and swapping it into an already running PC.)
If the laptops don't have encrypted drives...
-Whether the laptop is on or off, data can be pulled by another OS, allowing tools like Cain & Abel to potentially work some magic.
So, in closing:
- Require full disk encryption of laptops (e.g. TrueCrypt)
- User passwords should be at least 8 characters and contain combinations of uppercase, lowercase, numbers, and/or special characters.
- Passwords should change regularly (e.g. 120-180 days)
- Use an approved password manager.
- Last but not least educate your employees. Explain the basic risks of password loss and cover that protecting the company/network is part of every user's duty. Include basic practices like not plugging in strange USB devices, not leaving unattended systems logged in, and not writing down passwords.
***This typically doesn't have "much force" coming from the IT department. It's important that your company's executives/owners buy into this last point, understand it, and promote it company wide with their authority.