I can't say I've tried but you can find examples in the Illustrator menu where Adobe is doing just that (e.g. Type > Insert Special Character > Symbol > Bullet). As a general rule, if built-in functionality does something, you can usually do it too as they use their own API for 90% of the product.
Also, looking at the API, I can't see why it shouldn't work.
Sorry, that in response to the second question. As to the first, yes, you can add to Illustrator's menus. You kind of have to, and they've got a header, AIMenuGroups.h, that lists all the sets of menus in the product. Note that, say, the File menu has several menu groups in it, so depending on where you want your menuitem (or submenu I'm guessing) you'd have to figure out which menu group corresponds to where you want it to go.
We add a submenu to the kOpenMenuGroup ourselves, so that part is 100% doable. The submenu-of-a-submenu I'd be surprised if you can't do it.
Yes! I tried and it works!