Check out the Messenger Plus! Scripting Documentation - Specifically this page:
Events Reference > Messenger Plus! Events > OnGetScriptMenu.
What you need is to place your menus in the OnGetScriptMenu event rather than the ScriptInfo.xml file. This event is called whenever one of your script's menus is accessed and hence you can change it during runtime by adding the appropriate code in this event.
Also, checkout my post at
http://shoutbox.menthix.net/showthread.php?tid=56747&pid=636090#pid636090 for a more user-friendly way of generating your menus at runtime.
/ 
