OK, I've figured it out. The general idea was to copy the new parts of the database to the old one, thus having a fully working database. Throughout I refer to the "old" photos/database as the one that worked before removing the storage, and the "new" photos/database as the ones that work after a certain date (which probably has a different storage location, or were added after photos were deleted) but where the "old" photos don't work properly. Hopefully this makes sense. :)
For this to work, you need to have already made backups of the Shotwell database. So I'm assuming you know a little about where that is stored.
Preparation
Make backups of everything! I'm not kidding, there are no guarantees this will work.
The first step is to install sqliteman
sudo apt-get install sqliteman
After that, open your back-up Shotwell database using Sqliteman. Then enter this into the input box:
SELECT id, filename, flags FROM phototable;
Press F9 to run the command. You should see references to all of your photos appear in the scroll box. Scroll to the bottom, and verify that the last photo has a "flags" field of "0". This indicates that the file is present and working the last time Shotwell ran.
Make a note of the last ID value. Let's call it "phototable_max".
Now, delete the previous command and run this one:
SELECT id, filepath, flags FROM backingphototable;
This shows you all of the edits you have made. Again, make note of the last ID value. Call it "backingphototable_max".
Again delete the command and run this:
SELECT id, name FROM eventtable;
You will see the list of events. Once again, note the last value. This one is "eventtable_max".
This is getting a little repetitive, but now delete the command and run this:
SELECT id, name FROM tagtable;
Note the highest value. "tagtable_max".
OK, so now we have the ID numbers that worked in Shotwell before we broke it. After this point I'm assuming that the database works - i.e. after the point you made the backup all of the photos were not marked as missing.
SQLite time!
Now to copy the new database into the old one.
Definitely make several backups of your backups. There is a fair chance you will mess this up. You don't want to lose your Shotwell database forever.
OK, close Sqliteman. It's time for some CLI work. Here I am assuming that your old shotwell database is located at "~/.local/share/shotwell-old/data/photo.db" and the new one at "~/.local/share/shotwell-new/data/photo.db"
sqlite3 ~/.local/share/shotwell-old/data/photo.db
Now you will have an SQLite prompt. Into this, enter:
ATTACH "/home/sean/.local/share/shotwell-new/data/photo.db" AS new;
Don't forget the ; and obviously replace "sean" with your username. And yes, you have to use the full path.
Now we can just do these commands, and you're all done! You have to replace the _max values with the ones you noted earlier.
INSERT INTO phototable SELECT * FROM new.phototable WHERE new.phototable.id > phototable_max;
INSERT INTO backingphototable SELECT * FROM new.backingphototable WHERE new.backingphototable.id > backingphototable_max;
INSERT INTO eventtable SELECT * FROM new.eventtable WHERE new.eventtable.id > eventtable_max;
INSERT INTO tagtable SELECT * FROM new.tagtable WHERE new.tagtable.id > tagtable_max;
DELETE FROM videotable;
INSERT INTO videotable SELECT * FROM new.videotable;
What we are doing here is copying across all of the newer values into the old working database from the working part of the new database. The last two lines delete and then copy the videotable, which sorts itself out just fine when restoring missing files.
Then press Ctrl+D to close the sqlite3 interpreter.
You can now move the photo.db file to the Shotwell location, at "~/.local/share/shotwell/data/photo.db" and open Shotwell and it should all work! Make sure you have your hard drive or external storage connected this time.
I found Shotwell ran a little slowly once I first opened it, but it did eventually re-cache everything and got going again.
Also, note that I think because of how we copied the tags table and existing tags applied to new photos would have been lost. Any new tags should survive though, and likewise all old tags on old photos would survive too. This is because of the strange way Shotwell stores tag information - each tag record in the database stores which photos it tags.