Firstly, although it is difficult to do, winning an election (and even multiple elections) is definitely achievable as I’ve done it! Some of the missions are harder to play than others. Freedonia for example is one of the easier ones.
While I cannot identify what your exact issue is, a few points I would make. Firstly, all voters fall into a number of groups - a voter is not just a socialist, he may also be a smoker, a liberal and a motorist. Thus it is all well and good pleasing your socialists (if you, say, have a large percentage of them), but remember that all the socialists may be annoyed because of your policies on motoring, or smoking, or whatever. You can see the full implications of this in the “focus group” section, where you can see a focus group of, say, socialists, and you will see that their support can vary significantly, depending on what other groups they fall in to.
Also, do not focus just on dealing with situations. Have a look at how much of an impact the situations are actually having. For example, I always find that contagious diseases has one of the most significantly negative impacts, so focus on solving this quickly. If a situation is only having a small effect, or mainly affecting groups that do not really matter to you, you may wish to focus on other things. Increasing the GDP or literacy or decreasing poverty, etc. etc. may be more worthwhile in the short term than dealing with a particular situation. It all depends on what effect the situation is having and what your priorities are. My priority generally is a really high GDP, which probably reflects my political views, but you may decide to have a different focus.
Also, have a look at what effect events and dilemmas may be having. A terrorist attack will have a significantly negative effect on your support in the short-term. If you seem to be underachieving, it may be that an event such as this has occurred and is therefore depressing your “true” support.
As for party support, again, I can only go off my own experience that it is doable - try to maintain consistency by focussing on the same groups and the same aims for a length of time to help increase party membership. In many of the scenarios you do have a long way to go to catch up with the other party, and this can take a few terms, but, as I said in my previous post, if this was not the case then the game would not have much longitivity. Basically, be aware that things will not change overnight - it will take years (in game terms!), maybe even decades to put everything right and turn your country into a utopia. Remember, in real life voters can be very reluctant to desert a party that they have supported for many years, maybe their parents and grandparents before them supported also. You will have to work very hard to win them over.
On the subject of groups shrinking, have a look at what policies you have in force that may be causing that and at what policies may increase group membership. For example, with farmers, there are a number of policies under the “economy” heading that both increase support from farmers and increase the number of farmers - a winning combination!
Hope this helps.