What does it mean when software is only provided with the following legend: "Copyright (C) 2016 John Doe Inc. All rights reserved."
What are exactly the legal consequences of "All rights reserved"?
Let's say I want to provide my SW to a customer w/o granting him any rights? No source code sharing (only object code - SW is a JAR file).
Do I still need an additional SW License Agreement or is the Copyright notice above + a Disclaimer of liability sufficient?
What are exactly the legal consequences of "All rights reserved"?
Almost none. You have to explicitly grant copyright rights. You don't even need the Copyright notice for them to apply. My "almost" is because the notice makes it harder for somebody to argue "they didn't realize".
Do I still need an additional SW License Agreement or is the Copyright notice above + a Disclaimer of liability sufficient?
If this is free software (I know you said it isn't), do yourself (and everyone else) a favour by picking a license you like. Preferably either GPL or MIT (depending on your taste). There are far too many free licenses already. Please don't add another. (It also makes it much easier for any user of your software: "Oh yeah, GPL v2. We understand that. We can use it." as opposed to "What are the implications of using this one??"
As this is not free software, I think you need a paid-for lawyer (who understands IPR in your juridiction.)
Edit: In principle, I believe you don't need anything. The code is copyright, so the customer can't do anything with it (without explicit permissions that you haven't granted). However if the customer doesn't realize that or thinks you won't mind, you then have to go to court to enforce your rights (and probably end up with a disgruntled customer). A short, clear, license will make it clear to the customer what they are allowed to do, and save all that aggravation.
If the customer has no right to exploit the copyright in the software, they can't even run it. How can you run software without making at least one copy of it in memory? Perhaps in theory it can be done but that isn't how your average computer works.
As to loading software into memory constituting a violation of copyright, see MAI Systems Corp v. Peak Computer Inc (1993) 991 F.2d 511 (defendant, who was not a licensee in relation to software, ran software and in doing so created copies of the software in memory; the person was purportedly authorised by a licensee to do so, but the licensee did not have the right to so authorise the defendant).
However, in the US, this is now covered by legislation. 17 USC 117(a) says that it is not a violation of copyright in software to make a temporary copy for the purpose of running that software (including by a non-licensee with the permission of a licensee). In Australia, section 47B of the Copyright Act 1968 (Cth) is of similar effect (but also authorises running for the purposes of studying the program etc).
Furthermore, you probably granted an implicit copyright licence to allow the customer to run the software. Your 'All Rights Reserved' is unlikely to be read so as to exclude the existence of such an implicit licence.
However, your implicit license to the customer is unlikely (depending on what has transpired between you) to extend to allowing the customer to (for example) send copies to friends. So copyright law is probably doing what you want without you doing anything more.
If you are worried about things like decompiling, then copyright by itself is unlikely to help you (due to exceptions for fair use/fair dealing: see, e.g., Sega Enterprises Ltd v Accolade Inc (1992) 977 F.2d 1510) and so you would need to obtain the customer's agreement to a licence including a contractual promise not to decompile/etc.
You have already mentioned a disclaimer of liability.
I can't think of anything else that is customarily covered in software licences. Some cover patents but that's usually for the benefit of the user/customer, not the developer, so you don't need to worry about it in this case.
I would echo Martin Bonner's practical advice to include a licence if for no reason other than to ensure everybody in fact knows what is expected of them and there are no surprises.
