Well, I ran a naval campaign for about two years set in Scarred Lands, so I have a bit of experience with this. The SL answer to teleport is that the ocean is poisoned by the blood of a Titan, so teleportation has a significant chance of death.
There's a number of issues to be aware of.
First off, nerf the Lyre of Building. Making your ship immune to all damage for half an hour is just too powerful.
Secondly, you need to decide the technological level of the ships. Since your talking about transoceanic voyages, you're probably looking at Carrack era or later. (Think the Santa Maria). The effect of this is that the party's money gets tied into the ship pretty thoroughly. The ship is worth several tens of thousands of gold and the cargo may be double or triple (or more depending) of that. That's how I tied my players to the ship. I locked their cash into the ship. On a side note though, shipping winds up with absurd amounts of money. Far beyond the level of the characters. However, since the money is tied up in goods and a ship, it doesn't really affect game balance.
Another point, if you want a bit of realism - you cannot put a catapult on a sailing ship, nor can you put a ram. Catapults don't work because of the rigging and you simply cannot ram with a sailing ship. Doesn't work. Ramming needs oars.
Depending on the ship, you will be dealing with a crew of around 50 plus the party plus any troopies they decide to take. That's a whole lot of things to deal with. I suggest taking a gander at the mob rules in the DMG II for how to handle crew on crew action. I really wish I had had those rules when I was running the campaign.

As far as ship to ship combat rules, there are a number out there. If I could make a suggestion, take a look at the vehicle combat rules in D20 Modern. With a bit of tweaking, they might work quite nicely.
As far as spells go, beware any spell with a long range and the Extend feat. A wand of extended fireballs (7th level) has a range of about a 1/4 of a MILE (1300 feet IIRC). Purify Food and Drink is a must, but, if your ship is a carrack or larger, Create Food and Drink won't work. Too many people. Make Whole is another very useful spell. Gust of Wind is less useful simply because the duration is so short. Relics and Rituals for Scarred Lands has a number of naval spells that I highly recommend. Ship Snare is a fantastic option.
As a suggestion, I tweaked the counterspelling slightly. Normally, a dispel magic works as a counterspell, but only if the counterspelling mage is within range of the caster. Dispel Magic has a very short range when you are dealing between ships, and certainly much shorter than an extended long range spell, even if the Dispel Magic is extended as well. I tweaked things by saying that dispel magic could be used as a counterspell for any incoming spells, regardless of the range of the originating caster. Since Dispel Magic doesn't always work, it's still chancey. However, that knocked the primacy of the spellcasters down a few pegs. Make a wand of dispel magic a standard feature on larger ships and your mages can't simply rain fire from afar on the enemy. On the flipside, neither can the enemy.
Just a few ideas.