But I also wonder how the fact that other Presidents have issued similar orders would factor in to a Court's decision to hear the case as a general violation of the 4th Amendment.
I'm not aware of any specific orders that reached outside of FISA, except for the warrantless physical entry into Aldrich Ames' home (FISA had no such provision at the time, it does have one now). The issue wasn't litigated, Ames' plead guilty. His lawyers planned to object to evidence gathered during that physical entry and search, BTW.
The fact that there is a body of cases isn't helpful to a putative plaintiff. Put yourself in there, could you bring a case? How do you know you were the target of surveillance? If there is a violation of the 4th amendment and the target isn't aware of it, is it really a violation?