As you can see in the manual, what you store is either a link to a particular message (from message-view) or the last know query to it (from headers view). I guess the latter, the query, is what gives you trouble.
To avoid that, with the minimum fuss you can, either:
Link from the message view.
Refile first, then link.
or with a little work, pack ...
Old question, but since it is the first thing that pops up in google (at least for me), I guess it is worth updating.
The answer provided by @miguelmorin no longer works (see C.4.9 in https://www.djcbsoftware.nl/code/mu/mu4e/Writing-messages.html). You now have to use mu to register your email address (with mu init --maildir=/path/to/mail/folder --my-address=...
To open a link from a string:
To make the stored link the latest kill in the kill ring:
(advice-add 'org-store-link :after
(lambda (arg &optional interactive?)
(when (or (eq major-mode 'mu4e-headers-mode)
(eq major-mode 'mu4e-view-mode))
The answer was in that same tutorial with the use of contexts:
:match-func (lambda (msg) (when msg
(string-prefix-p "/Gmail" (mu4e-message-field msg :maildir))))
(mu4e-trash-folder . "/Gmail/[Gmail].Trash")