I want to delete the Startmenu\XXX folder and Program Files\XXX menu upon uninstall for the application.
Tried RMDir /r but this does not work for me.
(Windows 7)
RMDir is the correct instruction, your path is probably wrong.
A common issue with startmenu removal is forgetting to use RequestExecutionLevel, see this page on the NSIS wiki
Process Monitor can help you detect path and privilege issues...