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