Prefix "a" in "amaze"
Solution 1:
The Online Etymology Dictionary reports the following:
early 13c., amasian "stupefy, make crazy," from a-, probably used here as an intensive prefix, + -masian, related to maze (q.v.). Sense of "overwhelm with wonder" is from 1580s.
So the a- is a prefix here, but it intensifies instead of negating. Wiktionary lists the several uses of a- and notes the Greek-based meaning you cite as the only one that remains productive today.
Solution 2:
I'm surprise that Wiktionary does not have a sense of "to the" which I have understood to be another use of a-.
And I think it's productive, as well, as I use it to make new words, though admittedly ones that sound archaic.
How about ...
a-swimming we will go...?
Usually hyphenated, this would be my understanding of the use in amaze: "to the maze" = "to confuse my mind (with the sheer wonder of it!)"
Is there no reference that agrees with this?
Solution 3:
See etymonline (http://www.etymonline.com/index.php?term=amaze):
early 13c., amasian "stupefy, make crazy," from a-, probably used here as an intensive prefix, + -masian, related to maze