All I can say is that I sympathize, because I've had this same problem, and I couldn't find a decent solution to it.
In the PageMoving event, there's a TargetLink property. You can check if this is PageReference.WasteBasket. This seems like it would work, but I've always had trouble with it.
I can't remember the last time I wrestled with it, but I think that the e.Page item is null when something is coming out of the Wastebasket.
I do remember that I finally gave up and just told my users to republish pages after moving from from the wastebasket, so my PagePublishing code would run.
You can cast the eventargs to MoveContentEventArgs and then check the property MoveContentEventArgs.OriginalParent and compare if it is equal to wastebasket
In Global.asax.cs I need a way to figure out whether a page is being moved from the recycle bin to some other place in the tree. The only possible way to detect this as far as I know is to traverse the tree all the way up to see if it goes to PageReference.StartPage or PageReference.WasteBasket.
Is there any better way?