@john: The laptops have Lenovo ThinkVantage Power Manager installed, but there are no settings for what start > shut down does. I will try without this active when I see the problem again however, thank you.
@Domino: All of the options on there are set to Sleep - there aren't any options to log the machine off when the action occurs, only Sleep, Shut down and Hibernate.
The setting to require a password after wake-up is set as on.