How expensive may it be to destroy all long s-t paths in a DAG?
[Self answer; this is a shortened version, the old one can be found 
here]

We realized with Georg Schnitger that the answer to my question is strongly negative: there are DAGs
(even of constant degree), where every $k$-cut must have a constant fraction of all edges, not just an about $1/k$ fraction, as in my question. (A slightly weaker result that a $1/\log k$ fraction may be necessary can be obtained by using a much simpler construction mentioned in the footnote above.
A quick write-up is here)

Namely, in the paper 
"On depth-reduction and grates", Georg constructed a sequence of directed acyclic
graphs $H_n$ of constant maximum degree $d$ on $n=m2^m$ nodes with the following property:


 For every constant $0\leq \epsilon &lt; 1$ there is a constant $c &gt; 0$ such that, if any subset of at most $cn$ nodes is removed from $H_n$, the remaining graph
contains a  path of length at least $2^{\epsilon m}$.


Take now two new nodes $s$ and $t$, and draw an edge from $s$ to every node of $H_n$, and an edge
from every node of $H_n$ to $t$. The resulting graph $G_n$ still has at most  $2n+dn=O(n)$ edges.


For every constant $0\leq \epsilon &lt; 1$, there is a constant $c ' &gt; 0$ such that, if any subset of at most $c'n$ edges is removed from $G_n$, the remaining graph
contains an $s$-$t$ path with  $2^{\epsilon m}$ or more edges.


Proof:
Call the nodes of $H_n$  inner nodes of $G_n$.
Remove any subset of at most $c'n$ edges from $G_n$, where $c'=c/2$.
After that, remove an inner node if it was incident to a removed edge. Note that
at most $2c'n=cn$ inner nodes are then removed. None of the edges incident to survived nodes
was removed. In particular, each survived inner node is still
connected to both nodes $s$ and $t$. By the above property of $H_n$, there must remain
a path of length $2^{\epsilon m}$ consisting entirely of survived inner nodes.
Since the endpoints of each of these paths survived, each of them
can be extended to an $s$-$t$ path in $G_n$. Q.E.D.


 A consequence is sad:  there does not exist any analogue of Markov's lemma for functions with many short minterms, even though the set of long minterms has some "complicated" structure: no super-linear lower bounds on the network size can be then proved using this "length times width" argument.

P.S. This "length times width" argument (when all $s$-$t$ paths are long enough) was earlier used by Moore and Shannon (1956). The only difference is that they do not allowed rectifies (unlabeled edges). So, this is, in fact, a "Moore-Shannon-Markov argument".