I've tested the problem and the update method that works correctly is this:
1. Download paid ZIP package through our E-Shop -> Download area
2. Go to your Joomla administration and open Extensions -> Extension Manager -> Install page
3. In the Upload Package File section, select the downloaded ZIP package and click Upload & Install button
JoomSEF 4.0.9 should be correctly updated to latest version.
We were changing the update process starting from 4.1.0, so versions older than that must be updated using this way, other ways don't work.
But as you said that this doesn't work for you with HTTP 500 error, it seems there's some problem encountered on your server. Please check your server's error logs to see what the problem is and post the reported error message.