I went through the same pain. Win64+php-x86. It ended up being something relatively simple to fix - it is all about paths.
I first had installed the full ImageMagic-x64, then eventually the extension. I later noticed that installer had appended ImageMagic in the beginning of the PATH.
Just in case I tried with the x86 version and got different errors about missing DLLs.
So, just in case I uninstalled ImageMagic completely and cleaned up all references to it from the environment (it was in the PATH and MAGICK_HOME).
Then I installed just the extension (in my case from http://windows.php.net/downloads/pecl/releases/imagick/3.1.2/ I got php_imagick-3.1.2-5.4-nts-vc9-x86.zip) and unpacked it in the ext folder.
The revelation came after I tried to run this from the command prompt: php -i and got an error that it could not find CORE_RL_wand_.dll - but I did see it in the ext folder!
Adding C:\Progra~2\PHP\EXT at the end of the PATH environment variable solved it (after making sure that there are no other DLLs interfering).
Note: I used the 8.3 path to "C:\Program Files (x86)\php\ext" - just in case as I've seen PHP being sometimes picky and unable to resolve paths with spaces in them.
Also - after messing up with the PATH you may have to reboot the PC - in my case it worked from a command prompt right away, but IIS had a cached (older) path.
In conclusion: I suspect the PHP extension relies on some DLLs (which it delivers as part of the ZIP) but the same ones are also part of the standard ImageMagick installation, except that the two are not exactly the same - if you happen to be loading the wrong ones fun things happen...