Okay, lets say decks after 2000 then.
That's easy. If you count decks from all makers, I'm guessing that T11's Sentinels would be the first. If you're talking about indie-made decks, it might well be the Vortex deck. This assumes the definition of "fully custom" as being "unique backs and custom-designed faces only loosely based on standard Anglo-American design, bearing unique pips, unique court characters and at least some unique spot card configurations." I can't recall off the top of my head anything else that fits from earlier than that. Though if the original JAQK Winery decks are original enough - and they may be - I'm thinking they may have come first.
Mind you, this is only picking from decks we know about from around here. E's first truly custom job was not until, well - Artifice probably comes closest, though the courts are based on standard courts and the pip configurations are pretty standard. T11 had the Sentinels, and precious little else. D&D - maybe the Ultimate Deck was their first. TBC's closest would be, I think, the Vaudeville deck, and HOPC's would probably be the Curator, though one could argue that all the modifications are based on standard pip designs and that it wouldn't count...
Were it not for the backs being based on the Rider Back, the Bicycle Tragic Royalty might be USPC's first since 2000...
If you apply the strict definition of fully custom, precious few decks made since 2000 actually qualify...