The pemi loop is one of my favorite hikes, but its not very remote. Honestly, its hard to recommend a hike that I can guarantee you ultimate solitude on… however, here are some suggestions for 4-5 day hikes in the ADK:
1) Northville Placid Trail in the west canada lakes wilderness – if you like fishing this is for you. Bring a packraft to explore lakes if you want. There are many offshoot trails around the area. Cedar lake is a great destination. Make a loop of a few trails and a small mountain if interested.
2) Santanoni range with a trek out to duck pond, loop back around the other side of Preston ponds – take the Tahawus road that would take you to upper works, but park at the first lot for Santanoni and duck hole. Hike back to the santanoni lean to and walk passed it to find the campsite on the opposite side of the trail. Day two do an epic peak day to santanoni, panther, and if you have the balls, add in couchsachraga. Its a tough day! Day 3 pack up camp and hike out to duck hole. you'll have to hike around to cross on the cold river "horse trail" if the water is high, the dam and bridge for duck hole washed out a few years back. Decide if you want to take it easy and camp near there or start to turn east and then south again to go around preston ponds and take the trail back toward henderson lean to. hike out from henderson lean to, just a few miles to the upper works lot, and then walk the last mile or two on the road back to your car. this is very remote for the ADK.
3) Circumvent the seward range. This is the most remote trip I've ever done in terms of people – saw some on horseback going in, then no other people for 2 full days. Please see the link to the trip report I wrote about it last year:
http://www.backpackinglight.com/cgi-bin/backpackinglight/ul-compromises-adk-wilderness-klagsbrun.html#.U_5_rUhGzy0
I'm actually about to hop in the car and head back there tomorrow AM to finish the job and get Seymour done before the rain hits on Sunday.
4) If you don't mind seeing plenty of people – I cannot recommend enough an attempt of the great range in the ADK mountains. You can always just camp anywhere along your route as long as you follow the simple rules about distances from trail, water, and altitude. You'll have plenty of time and the views are the most incredible around. At the very least try Haystack, Marcy, saddleback and Basin. You won't be disappointed. Base camping in any of the valleys will allow many day hikes to the gothics/armstrong/wolfjaw loop, as well as many others. Check out ADK high peaks forum for mmore info!