The consensus algorithm BABE assumes that at least one block will be produced per epoch, so probably you stopped your nodes and whenever there is a period of inactivity (no blocks being produced) for more than one epoch BABE is broken.
Because you are in development the best solution for that is to clean the database as you have tried. However I think you are trying to delete the wrong folder, if you are running the same commands as the tutorial you are using the following flag:
--base-path /tmp/relay/alice
Which is specifying that the chain database stored locally at /tmp/relay/alice
try to delete this folder and the same for the other Node Bob.
Another option when you are in development mode is to use the flag --dev
because each time you start/restart a node, this will create an delete a temporal folder for the DB.
You are not able to create a paraId
because of this issue, when fixed if you follow the step-by-step guide: Connect a local parachain it will work.