В обоих случаях правильно «на Мальте» и «на Сейшельских Островах».
Слово острова пишется строчными в значении 'группа островов, архипелаг': Сейшельские острова, Маршалловы острова, Виргинские острова. Но в официальных названиях государств, административных территорий слово Острова пишется с прописной: Республика Сейшельские Острова, Республика Маршалловы Острова (названия государств), Британские Виргинские Острова (название британской заморской территории).