Why is Bluetooth tethering a must have? It's not only slow, but it's also detectable by your provider (which could be problematic if you are not on a tethering plan).
You could use EZSpot or JoikuSpot to tether via WiFi to get better performance, and less chance of getting caught (if you are not on a tethering plan). EZSpot is < $3 and works great.
I also noted that you listed a real keyboard as desirable and not must have. With that in mind I'd suggest you consider the N8 as an option. It's solidly built, has good battery life and an amazing camera (the best until the 808 comes out). 12MP, Xenon flash and auto-focus. Yes, typing on a touchscreen can be a bit frustrating, but many swear by a utility called Swype that allows you to type by just sliding your finger over the screen.
As for IM clients, there are a number of them available now. Fring and Nimbuzz are my favorites. Both will IM over multiple systems (AIM, MSN, ICQ, etc.), and Fring does video/voice calling too (and it's available on Andriod and iOS as well, so it's cross platform). Skype has an official app, but it does not support video on Symbian (only text chat and voice calling).
The N8 meets most of your criteria.
1. Quad-band GSM with at least UMTS bands I, II, IV & V (2100, 1900, AWS & 850) must have.
The N8 was the first Penta-Band 3G phone, so it will work on any GSM network for both voice and 3G data (with the exception of proprietary networks like Tracfone and Net10).
2. WiFi & Bluetooth with tethering by BT. (must have)
Yup, but I'd still recommend using WiFi tethering with EZSpot or JoikuSpot.
3. Real keyboard. I'm terrible with touch screens. (desirable)
Touch screen only, sorry, but Swype helps a lot of people get over it.
4. External antenna jack (always desirable)
They actually make phones with an external jack? I did not know that. The N8 does not have one, and I'm pretty sure your other choices don't either.
5. Good suite of available communications apps (VoIP, Skype, Facebook, VPN, IM, etc). (Must have) I'm not into games, so I don't really care about Angry Birds and apps like that. Barcode scanning would be nice.
There is a built-in social network client, but most people say that an app called Gravity is the best. I've already covered IM above. There are a number of barcode scanners as well, and the N8's camera works well with them. I don't do any VPN so others will have to help with that, but you can play Angry Birds :P
6, 7 & 8. Supports Java, Camera is awesome (best on any phone except the Nokia 808 Pureview), and battery life is very good.
There are 10 types of people in the world: those who understand binary, and those who don't.