Well this all boils down to what a node is. A node is a compacted computational unit tht does something with inbound connections. As a design rule a node must obey this, so a node is not supposed to fetch things from outside itself or its not known when the node is executed.
Now a expression is a custom node. In way it has to obey the rules of the dg. However it was very early discovered that users wanted to execute arbitrary code. Now maya does not disallow this, not even in the api you can do whatever you want even if its not smart. However once you stop conforming to this maya stops helping you, and starts fighting back.
The inherent property of a node that obeys the rules is that it will be connected to the network, it is also aware of when it needs to update, and updates correctly. Now a node that does not follow the rules is a complete rogue and can do whatever. for this reason they added the always update to expression nodes (needless to say there should be no need for it).
So how do they differ, well quite much expressions are not mel (allmost everybody misses this until pointed out), the expression node supports using if so called expression language, its not mel and they get precompiled when teh expression is entered into the node.
somenode.Someattr=someOtherNode.someattr+someOther.someattr;
While you could do the same with mel YOU SHOULD NOT DO THIS:
setAttr somenode.Someattr (getAttr somenode.someattr+getAttr someOther.someattr); //DONT DO THIS
One often sees mel used nevertheless, sometimes because the explression engine a is a bit brain dead and allows no loopping. Sometimes because they don't know better. And mostly because people aare lazy buggers.
So it is safe to say that theres something wrong with a expression if it contains any of the following commands.
getAttr, setAttr, xform, move, rotate ,scale...
And theres something even more wrong if they use soemthing like (thsat is unless the maker of the script was VERY VERY enlightned and this was the only way, or its marked as quick and dirty):
extrude, loft, createNode, delete
One also sometimes sees expression used as a replacement for scripjobs... Well its halfway sane. Howevr if you dont clean them up you will end up with a LOT ofnodes.