On my computer, whether Skype is minimized etc. doesn't seem to matter. The workaround solution is always the same: send the first Skype chat msg twice. Or rather, send 2 messages one after the other. The first message can be blank.
The 2nd message always generates an event for me, no problem. And after that, every chat message sent generates an event as long as there is no extended interruption -- say, 10 or 15 mins.
The issue is on the Skype side (if you look around the Internet, you'll see other programs currently have the same problem with the Skype api and nobody can figure out a solution), and I doubt Microsoft will address it.
In terms of "other solutions" apart from Skype, it depends what the goal is. If you mean other solutions for communicating with VC remotely, various possibilities have been posted before.
As mentioned above, you can create a TCP listener. To access it beyond your LAN, you'll need to use port forwarding and not everyone is comfortable doing that.
Setting up a VPN is another option.
Android users can try the Tasker route.
Or, one could customize the gmail notifier python code I posted the other day, but if you want instant responsiveness this may not be ideal.
Again, if instant responsiveness is not required, using IFTTT with the new Watcher plugin is also an option.