I took a look around the Developer Guide and API Reference and nowhere in either of them could I find any guarantee that the instance id would be unique among all availability zones.
The only link I could really find online (besides the one you posted) was this serverfault question which includes a post by a guy named 'jedberg' who says he contacted Amazon support and asked whether you would ever get a duplicate instance id. Their response was:
"Instance ids are unique. You'll never receive a duplicate id. However, the current format of the instance id is an implementation detail that is subject to change. If you use the instance id as a string, you should be fine."
Which doesn't specifically say that they're unique per availability zone, and does say that they make a guarantee to provide a unique instance id.
Given no concrete indication either way, I'd err on the side of caution and assume you could receive a duplicate in another availability zone. If you're really not sure, you may want to put a request in with Amazon support to ask for clarification (and post their response here!).