Having recently encountered issues with features not being installed correctly when you are trying to deploy an updated version, I think I have stumbled upon the secret recipie to success:
Deactivate the feature at the appropriate level
Run uninstall.bat to uninstall the feature from any sites where it has been installed.
Copy the new wsp file to your deployment folder
Run install.bat to install the feature to any sites
Wait for a minute, as elements of the site will have been restarted during 4 and rushing causes problems
Reactivate the feature
Clear your browser cache
Shift-refresh the page with the feature on it to be sure of the latest version
This process seems to fix the problems of new items in elements.xml not being made available to site collections where the old version of the feature had previously been deployed.