Can anyone help with this? - Can Recaller record Skype calls, either automatically or manually?

The answer is yes.
Skype or any other calls, are just calls and will be recorded.
Just try it.

I've noticed that some phone calls are recorded correctly from ringing to hangup, whereas for some of them the recording starts a few seconds after the conversation is already ongoing, or record a few seconds after the hangup. What could be the reason for this?

Recaller widget after the installation is not in the menu area, or displayed on the desktop.

No, but it appears on the list of widgets. You need to add it to the desktop manually.

There is one problem that I've found with it though. When a phone call is placed while the device is in mass storage mode, it does not record anything (as expected!), but then keeps popping up a yellow banner "recording since..." every time you switch to the desktop. Another call after disconnecting from mass storage is recorded, but the pop-ups do not go away. I've had a situation when I had them for days until I lost patience and rebooted the phone.

EDIT: I finally found the time to read the whole thread. It turns out the bug described in the above paragraph has been noted before (4 different links).

EDIT 2: I've also found that when you ring up someone but hang up before the other party answers, recaller continues recording until you start and finish another call. This bug has not been noted but I assume it's just a different manifestation of the same thing.

The manual addition I know I can work with applications I already had it installed. Now my phone after the factory settings and I recorded only CSSU Beta and still not working. It seems to be installed, but the possibilities of adding widgets to the desktop menu is not. I do not know how to force application "is displayed".