So in the game I'm working on, part of it is you recruit NPCs onto your crew, and they move into your space ship as you travel around the galaxy. The NPCs all have their own schedule while on the ship - they can go to the weapons range to practice, to the observatory to stargaze, etc in accordance to a Clock object's Clock.Minute and Clock.Hour.

However, in the recent thread 'What makes a strong NPC' I saw one of the listed qualities is 'The NPC doesn't move around pointlessly' so now I'm having doubts about this feature.

My question to you is - should I add a toggle-setting that Enables/Disables NPC Wandering aboard the ship? There's no wandering anywhere else.

As long as you can predict where each NPC will be when (or if) they are needed to progress in the game without having to start all over, it should be fine.

Plus, it sounds like your NPCs aren't moving around pointlessly. The way you describe it, they each have their own agenda.

NPCs that act independently sounds excellent. Do not be deterred!

Could you have a system where the player can ask the ship's computer where they are? Perhaps have them stay there for five turns after a request?

Here is how I would do "random" moving NPCs...
Each room has a direction "key" for places of interest. (Actually, I've described this before!)
IE: the main deck has 4 exits: fore, aft, starboard, port.
Where they lead, at this point does not mater.
An NPC wants to go to the galley because he is hungry.
The galley does not connect to the main deck, but, if he goes aft, he will get closer.
You would just need a list of places he would go, then he can follow the route from anywhere on the ship.
(Theorized, but not tested.)

The Pixie, that's a great idea. Intercom system implemented, tested, and 100% functional!

On my first attempt at a game (messing around learning the language) I had an NPC wandering around randomly inside her house. Not just moving the NPC randomly, but if she sees certain items out of the room they should be in she'd pick them up and then take them back to where they're supposed to be.

Was fun to work on, but when playtesting she was a little annoying.
With NPCs moving on a schedule it would at least be easier to find them if you want them. I'd suggest having each person's schedule on a notice board in their room or something; so you can look at someone's calendar and see where they're likely to be. Or presumably in a high tech world there's some kind of communicator system, so if you need them you can ask where they are and/or call them to come see you.

I think if it's trial and error trying to find somebody you want to talk to, that could be annoying. But if you can look up where they are, call them, or wait in someone's room until they get back, then I think it would be a great way to add immersion.

In X3, I’ve got characters that move places based on time of day. It was a pain to set up but the result is nice. Like mrangel said, knowing where “wandering” NPCs are is nice and trying to find them when you can’t is not so much fun.