The reference guide states for Double-Sided Cards that
When a double-sided card is discarded, it is immediately shuffled back into its respective deck.
The phrase "shuffled back into deck" is never elaborated on and I couldn't find any discussion on this related to Eldritch Horror.
The mechanic "shuffled back into deck" can mean two things
- insert the card at a random location in the deck
- add the card to the deck then shuffle the deck. This would also trigger the rule "another player cuts the deck"
The only explanation of this mechanic I could find is for HearthStone.
Shuffle into deck effects place cards into a player's deck, with its placement randomly determined. While not stated in card text, the randomness of the card's placement is achieved through subsequently shuffling the entire deck.
This would suggest that the deck should be shuffled when a player discards a double-sided card