If I understand your question correctly, you're saying that 59% of responses to the first variable are missing and 55% of the second are missing whilst the rest of the variables are fairly complete.
When you analyse complete.cases in R, you are excluding cases 'listwise' which means any case that has a missing value on one or more of the variable is excluded. This of course, results in most of your cases being excluded. This means that even if you are comparing variable 3 and 4 (which are mostly complete), you will still exclude lots of cases because they are missing values on variable 1 or 2.
One way around this is to exclude cases 'pairwise', which basically means you only exclude cases if they are missing values on at least one of the variables in that particular analysis. This means that you can then compare variables 3 and 4 for example, without excluding all of your cases.
If you are excluding cases pairwise (or listwise) you still want to be quite careful about analysing variables 1 and 2. Because you exclude so many cases whenever you run an analysis with variable 1 and/or 2, it becomes possible that the cases you included may be systematically different from the cases you excluded.
As an example, imagine you asked people what their average income is. A large number of people may not have responded to variable 1 because they were embarrassed for some reason about their income. Now if you run an analysis including only those people that responded to variable 1, you will unintentionally be excluding everyone that is embarrassed about their income and thus, your sample will no longer be representative of the general population (it will instead be representative of a population of people who are content/proud of their income).
The simplest solution then is to avoid analysing variables 1 and 2 at all. If you do still want to analyse variables 1 and 2 I'd recommend excluding cases pairwise and running a correlation analysis to check whether cases with missing values on variables 1 and 2 tend to systematically differ on the other variables. If they do systematically differ (or perhaps even if they don't) you could then look into doing some fancier stuff such as estimating values for variables 1 and 2 based on each case's value in 3,4,5 etc such that they are no longer missing values on variable 1 and 2.