I'm using iPhoto 08.
In iPhoto, go to the left-hand column under MOBILEME GALLERY and highlight the movie you want to delete. Then hit the Delete key. Then go to iPHOTO>Preferences>MobileMe>Check for new photos: Check Now. That should update your MM Gallery including deleted items.