OK I'm going to follow this up with a better solution, as the problem happened again today, and I spent 11 hours trying to fix it (lol), because I was unhappy with the 'brute force' approach above and wanted to know what was actually going on.
So I found out that Cubase identifies plugins with a class ID, which is a unique ID, a bit like a GUID. It generated this somehow - god knows how, Steinberg said it's based on the filename and VST ID (nebula magic number), but this doesn't seem to be the case....
After looking in my Cubase session files with a text editor (GVim), I found the class ID that is stored for Nebula3 Reverb: 5653546F3031306E6562756C61332072. I searched for Nebula3 then looked for a long string similar to this.
I then checked Cubase -> Plug-in Information -> Right-click, 'Export'. Look for Nebula3 Reverb here, and I found this class ID: 565354343632396E6562756C61332072. It's slightly different. I noticed by changing the VST ID (magic number) in Nebula's XML config, that the magic number is actually embedded in the class ID ('34363239' => remove the '3's => '4629').
Anyhoo, I used search and replace in my session files to replace the class ID that was stored, with what Cubase actually is looking for. This worked, and it recognised the plugin.
I'm surprised that not many other people have had this issue... maybe I'm just unlucky!