After submitting our bug report to OpenVPN, they have released a new version of their client software which seems to rectify issues (many thanks to James Yonan and Gary McCloud).
You may download RC11 here. This offers true Vista support and hopefully less headaches but as this is still brand new software, there may be bugs that we are unaware of. As such, if you are comfortable with RC4 or RC7, you can continue to stick with that.
Below is the RC11 changelog which details the problem:
2008.09.14 -- Version 2.1_rc11 * Fixed a bug that can cause SSL/TLS negotiations in UDP mode to fail if UDP packets are dropped.