OK, the problem here looks like it was access rights on the file that stores my dock contents.
Apparently, using TinkerTool to prevent changes to the dock sets the access rights on that file, and doesn't change them back when I disable that feature.
I'll open a question on superuser.com about what the correct access rights should be.
Basically, this fixed it:
sudo chmod 777 ~/Library/Preferences/com.apple.dock.plist
killall Finder
But I don't like the 777 preferences.
EDITED: OK, turns out that this is TinkerTool's doing. To prevent accidentally removing things from the dock, which I tended to do to begin with, I used TinkerTool to disable modifications to the dock. This changes the access rights on that file. However, if I disable that feature, which I had done, the access rights are not changed back to what they where before. As such, after changing the access rights above, restarting finder, removing the items, and then locking down the dock again with TinkerTool, the changes stayed.