We are using SAML based federated authentication in our org which works just fine. We have however a company specific desktop client application written some years ago in Java that, among other features, allows logins to Salesforce to view the user's opportunities. I believe this app is just using the old SOAP API login() call to login. So far, so good. I'm wondering how to implement the SAML based login flow with that. Is that even possible? And if it is possible, would I not have to change the login server URL from https://login.salesforce.com to https://my_orgs_name.my.salesforce.com ? Has anyone done this if at all possible?
You'll want to take a peek at Single Sign-On for Desktop and Mobile Applications using SAML and OAuth. There are several different directions you could take. The article mentioned here shows how Chatter and Connect for Outlook do SAML-based authentication over OAuth2. In theory, you could skip the OAuth2 part, but that makes controlling the landing a bit rougher.
So, without copying the entire article here, let's go over the basics: the program needs to open a WebView component or equivalent to the My Domain URL with the appropriate path specified to start OAuth2. My Domain will redirect the user to the Identity Provider to initiate SAML-based authentication. The IdP will then redirect back to the Service Provider (that is, Salesforce), which in turn will deposit a token at the callback URL you specify.
Now, to answer your specific questions (just in case there's any ambiguity at this point):
I'm wondering how to implement the SAML based login flow with that. Is that even possible?
Yes. You could probably get a functional prototype in a day's work.
You need to change the exact URL you need to hit; salesforce needs to know the org you're trying to log in to in order to call the IdP (SAML provider) correctly. Either you'll use something like https://login.salesforce.com?so=00DXXXXXXXXXXXX, or you'll use https://my_domain.my.salesforce.com/.
Since you have to change it anyways, you may as well use My Domain, since it is usually easier to remember. SAML cannot work correctly without using either of these methods, unless you start with IdP-initiated authentication, in which case, your app won't directly hit login.salesforce.com, but will be directed there by the provider (but again, this means you have to correctly detect the session afterwards, so the landing is a bit rougher).
Has anyone done this if at all possible?
Salesforce.com itself does this, so I'd consider that authoritative. I've "tinkered" with doing this in Google Chrome for a project of mine, but the code isn't very developer-friendly at the moment. The idea, of course, was to be able to log in to an org through Google Chrome to manage the metadata directly from the browser; using OAuth2 allows any org to directly use SSO if they want to, while still having it be compatible with my extension.
If you're insisting on using a IdP-initiated login (which skips the OAuth2 part), you can still specify a RelayState, which is effectively mapped to a URL once Salesforce finishes validating the authentication from the the Identity Provider; you can use this to redirect to a protocol hook in your app (e.g. sfdc-login-response://callback), which you should be able to hook in to. Once this happens, you can resume operating normally by using the token as a Session ID.