How ought I lock particles' rotation so that they always face their velocity vector?
This can be done using the Animation Nodes addon. I've made a node graph that makes particles orient to their velocity. It's kind of a hack, but basically the idea is to create an instance of the ship for every particle in the scene, and then rotate the instance according to the particle's velocity. So essentially, you're replacing Blender's particles with your own. Also, you should make the original particles invisible by going to Particle System tab -> Render and selecting "None".

Here's the node graph:


And here's a proof of concept using this node graph: