Hi. Two answers - "It depends" and "you're about to find out". Your notes were moved to the Trash notebook when the notebook was deleted. The notebook metadata was lost, hence your needing to re-allocate them to a notebook. I don't know whether any tags were also compromised - you might want to check that. But when the notes were "deleted", they were just moved; and - depending on your settings and connection at the time - that movement was synced with the server, so the web version would also have shown the notes in the Trash.
By moving them back again you've (at worst) synced a few bytes of metadata on their location - the notes were already on the server, they've just been moved back again. If any other devices have synced since this drama, they'll show the notes in Trash, and then after another sync, they'll move back. No fuss, definitely no drama. Evernote is of course aware that all this happened - it's just working as planned.
I could, of course be wrong... if so, you'll be able to tell me all about it when you next try Android...