the bottle-neck will be the communication.
There is no way I know other than the GSM network that might work for you.
So every bottle should at least contain:
- an arduino
- a GPS (shield)
- a GSM (shield)
- a sim card with enough prepaid account to send 1000 sms's
- a big battery that will work for a week
If the bottles are out of GSM range they are gone. 
Adding a SD card will increase the price 10% max so if connection got lost it still can log the GPS data until the bottle is found
You should do a feasibility test how far you can go offshore and still have GSM connection.