To solve this problem, Google Maps Labs added a feature called "short URLs" that shows short permalinks when you click on "Link". The nice thing about this feature is that it uses Google's URL shortening service, which is very fast, and URLs are more descriptive because they include "goo.gl" and "maps".
To get the full permalink, you need to right-click on "Link" and copy the location. Unfortunately, Google removes the embedding feature if you enable "short URLs". Maybe it would make more sense to show the short URL as an additional option.