Would it be possible to negotiate a key of 128 or 256 bits strength using Merkle puzzles?
The complexity required for the attacker to break the scheme is at maximum quadratic in the security parameter $n$. It is not enough for a secure cryptographic protocol where you want exponential complexity to break the scheme.

Say $n$ is the difficulty of solving the puzzles and $m$ is the number of puzzles. Alice needs to solve one puzzle in time $O(n)$ but Bob will need to look in his puzzles to find the correct key. He needs roughly $O(m)$ time. The scheme has then $O(n+m)$ time complexity.

For breaking the scheme, Eve can brute force all the puzzles, she then needs $O(nm)$ time complexity. If you want to have this complexity be around $2^{128}$ you need to send an incredible amount of puzzles and/or puzzles too hard.