"I think we might be talking about apples and oranges, here. I'm not sure how you would define the word prophecy, but i would define it this way:..."

That is possible, perhaps even probable.
At a most basic level, I would just say that a biblical prophecy is anything that is in the bible that makes a statement about the future or about facts they couldn't possibly know about otherwise.  However, there must be conditions imposed for me to consider it a 'valid' prophecy.
 

1)  The prophecy must be made BEFORE the events it prophecises!  For prophecies about a previous event or fact, the propheciser must not be able to possibly know about the event or fact they are prophecising about.  The reasons for this should be self-evident.
 

2)  It must have a date or time limit attached to it.  For a mere human making a prophecy I would probably be a bit more lenient on the accuracy level of the dating, but for a human channelling an omnipotent, omniscient propheciser, I think it is reasonable to expect a higher level of accuracy.  The reason for requiring a date is twofold.  It saves time in debating "Is this event what he meant?  Is that event what he meant?".  More importantly, it provides a key component of falsifiability.  Prophecies with dates that have come and gone can be obviously written off as false.  Prophecies with no date have too easy a "get out of jail free" card, and this makes them pretty weak in my opinion.  Prophecies with future dates at least give us something to look forward to, though I suppose that if the prophet wants his distant-future prophecy to be remembered, he had better make some good predictions during his lifetime!
 

3)  It must not be fulfilled by people who could have heard of the prophecy.  It would be preferrable if people, who naturally have an interest in the prophecies, had nothing to do with it.  An example would be "On the 3rd of June 2008 a pig will fly, under its own power, around the world visiting every major house of parliament and will be seen by millions."
 

4)  Ambiguity, vagueness, repetition, theatrics and poetry demonstrate a different purpose for a "prophecy", such as a Nostradamus style all-purpose prophecy, or intimidation purposes, or allegory.
 

5)  It must be correct!

I'm really sleepy at the moment, so I might have other reasons for dismissing a prophecy, but they don't immediately spring to mind.
How does the Tyre prophecy fare?  Not too well I'm afraid.

1)  As far as I can gather, the oldest copy of Ezekiel is on some papyrus called P967 and is dated at early in the third century.  This is WELL after Alexander the Great.  I, of course, concede that there is nothing to say that P967 is the original document, and I would actually be surprised if it was.  However, that being the case, who knows what the original wording was?  And who had control of the texts?  I don't think that those in control were unbiased!

2)  No date attached.  We can try to use the text itself to see what date was intended, and the most glaringly obvious is the name Nebuchadnezzar, King of Babylon, which at least gives us a date range to work with.  The prophecy did not come to pass within this particular date range.  It is clear from Ezekiel 20:7-12 that it was supposed to be Nebuchadnezzar doing the fulfilling.  The obvious defence is that Ezekiel also says "many nations" and though it is more parsimonious to suppose that this refers to the 'many nations' under the rule of Nebuchadnezzar, like the many nations under the rule of Queen Elizabeth today, it also potentially opens the prophetic window to "from now until the end of time"  which is just ridiculous.

3)  Fulfilled by people or a person.  Note that I don't believe that Alexander had heard of the prophecy beforehand.  That said, the evidence that you have pointed to for God having spoken to Ezikiel is that the prophecy "came true" but if that is the only evidence that is required, it equally well supports the speculation that Alexander heard the prophecy from some random source.  We know people spoke.  We know people spoke about prophecies.  We know Alexander spoke to people.  We know he lived and invaded in and around the areas relevant to these prophecies.  I want to repeat that I do not have evidence for Alexander hearing about the prophecy beforehand, and consequently do not believe that was the case, it is just a simpler explanation that matches with the fulfillment equally well.

4)  Ambiguity, vagueness:  "found" ???  Going by your defence of this, God could have been saying "The square will never be a circle" because it could not be found purely by definition of what it was.
Is the water going over the city, or is the city going under the water?  Yes I do think this is an important difference.
"throw your stones, timber and rubble into the sea."
"when I bring the ocean depths over you and its vast waters cover you"
Repetition:  "like the sea casting up its waves" "Out in the sea" "throw your stones, timber and rubble into the sea" "bring the ocean depths over you and its vast waters cover you"
"make her a bare rock. 5 Out in the sea she will become a place to spread fishnets" "make you a bare rock, and you will become a place to spread fishnets"
"pull down her towers"  "demolish your towers"  etc
Theatrics and poetry: Pretty much the entire passage you directed me to. http://www.biblegateway.com/passage/?book_id=33&chapter=26&version=31

5)  "You will never be rebuilt, for I the LORD have spoken, declares the Sovereign LORD."
""The location of the city of Tyre is not in doubt, for it exists to this day on the same spot and is known as Sur." (Katzenstein, H.J., The History of Tyre, 1973, p9)"
http://maps.google.com/?ie=UTF8&ll=3...&t=h&z=16&om=1
"Excavations have uncovered remains of the Greco-Roman, Crusader, Arab, and Byzantine civilizations, but most of the remains of the Phoenician period lie BENEATH THE PRESENT TOWN." http://www.britannica.com/eb/article-9074016/Tyre
(emphasis is mine)

So basically, this prophecy is a failiure as far as I am concerned.