I don't know if this helps you narrow it down, but the functionality works correclty in vanilla AutoCAD 2013. I don't have P&ID to test, sorry.
Also, a possible workaround would be to press R <Enter> at the Select Objects prompt to get the Remove Objects prompt. Does this let you select multiple objects to remove, by crossing, window, etc?
Thanks for letting me know that it works properly in vanilla 2013, this must be an issue specific to P&ID. I am only using the 2D drafting capabilities right now, have not yet implemented all the extra functionality specific to P&ID due to this issue.
Others who have had this desekect problem were using Civil 3D 2013, but their issue was resolved by changing variables in IOPTIONS and MAPIOPTIONS, which are not available in P&ID 2013. I even tried exporting my profile which worked so nicely from 2012 into 2013 but still, no dice.
Drafting and Design
Cambridge Chemical Technologies
I can confirm your report in P&ID 2013, but only while no command is active (which is a bug)
However, if I start a command (such as ERASE), and pick multiple entities, then SHIFT+Window (or SHIFT+Crossing) some of the selected entities, ALL of them in the deselection set are unselected.