Grady is right, Captain Andy is EXCELLENT! Very informative and alert to client's needs. Highly recommended! For Machias Seal Island, i'm not sure of current regulations but each one of the charter boats was allowed to land every 3rd day. You will need to make reservations early and plan on at least a couple of trips, fog or rain can be expected. The whale watching catamaran out of Bar Harbor cruises past Petit Manan Island, no landing but it can be very good for sea birds like shearwaters and storm petrels. (also whales...)
If you land on Machias Seal Island, be sure to get some pics of the Razorbills too.