I've been trying to update the From Address and Reply-to Address with a new email address. The update appears to work, however, when an alert is sent, SharePoint is still using the original email address. I've tried several different addresses and the original email address is always used. Has anybody experienced this before?
You have outgoing email settings at both the Farm level and the Web Application Level.
Normally what you set at the Farm level takes effect everywhere, however you can also make settings specifically at the web app level and these will take precedence.
I suspect that you're modifying the settings at the Farm level, but the alerts will pick up the old (unmodified) settings at the Web Application level.
Farm - Central Admin > System Settings > Configure outgoing e-mail settings
Web Application - Central Admin > Application Management > Manage web applications > [choose web app] > General Settings (toolbar) > Outgoing Email Settings.