IBM MQ Series does work with on a Microsoft cluster. It will work if you configure it as a generic resource using the cluster's virtual IP, however it works MUCH MUCH better if you download the service pack for clustering, (I think its MC74 or something like that) Follow the instructions and create a virtual Queue Manager under MSCS control.
I have set a few of these up and they are fanatastic. To give you an example, I started a AMQSPUT, rebooted the active node in the middle of it and within 12 seconds the secondary node had taken over, and MQ continued receiving messages, I sent 33 messages, none were lost.
With Active / Passive - No you do not need an additional license. The binaries reside on both nodes, but there is only one copy of the program running at any given time
With Active / Active you need 2 licences, its just like installing it on 2 NT servers right?