At last I got it working!
Made my first free call with Skype from a computer in Eastern Europe to US mobile, hit voice mail, called another number, this time in Canada, had a talk.

As it turns out, all you need to make free calls to US or any North American number from you computer is a fast reliable US-based proxy and appropriate egress filtering solution.

However, if you’ve read the previous paragraph carefully you can see that “free” comes at a price.

First, it is in no way trivial to get a reliable proxy, even for money, mind you.
The popular websites talking about easy Google searches akin “open public free fresh fast quality anonymous HTTPS SOCKS proxy US IP” mean only to entertain certain circles of script kiddies and ignorant paranoiacs seeking false sense of privacy.
Just think about it: who on earth (er, in US) in their right mind would set up a public proxy? No really, people who own/rent IP addresses know their responsibilities and definitely wouldn’t buy them just to give them out to strangers on the opposite side of the planet. And if such thing happens by accident (for lack of competence for e.g.) it won’t pass an hour till the victimized IP address gets blocked by an ISP up the road.
“Investigators” wishing to test their luck with intermittent proxies opened by operators’ mistake should be prepared to weed down substantial amount of data mined through Google. Or, it is possible to purchase lists of tested proxies (still I wonder if those proxies are of any usability…) but is it all worth it? Wouldn’t it be of less trouble just to purchase a Skype Credit in the end?

Note one special case though, when foreign proxy comes packaged with the working environment of the user. It is a user’s corporate VPN, or Virtual Private Network.

Now, suppose you’ve got a proxy and anticipate huge savings on calls already. Hold on, here’s the

Second requirement to be met: the Skype instance on your computer must be strictly isolated from the outside world.

Skype is known to be a bit notorious in circumventing all sorts of firewalls it encounters on its way out (and even ways in, though that’s completely different story). In that quest Skype defaults to get to the world by-passing any configured proxies as far as possible, so, deliberately or not, it will most likely reveal you local IP address and you’ll end up banned by Skype network from making free US calls.

The solution to this isn’t free if you’re on Windows. You’d have to either buy and install a third party firewall with good egress filtering capabilities (able to filter outgoing internet connections) or ask an upstream router’s administrator to set up blocking of all outgoing connections from your windows box except those to your US proxy.
The latter is a major headache, I’m telling you. And the former is a plain annoyance as well, given Windows XP built-in firewall (Internet Connection Firewall, ICF, or Windows Firewall) is pretty much sufficient for a common user. Yes, it has no protection against information leakage (i.e. has no egress filtering at all), but one can live with it more or less happily… until he or she decides to call for free with Skype, that is.

Of course, things are easier if you run Skype client on Linux. You just block all outgoing access for a user running Skype with a built-in firewall (inevitably free), which is a good practice for any human user anyway, even without Skype in mind.

Third, be aware that many proxying/tunneling techniques exhibit fairly ample traffic overhead. At least for some user groups this may present a stopping barrier by either raising the cost of use traffic-wise above Skype’s original per-minute rate or by over saturating the network link above its bandwidth heavily degrading voice quality.

In brief, this experiment’s value is rather academic, not utility. Yet in some cases it can be a life-saver, like when you already hold all the infrastructure needed for the process, but, for e.g., can’t buy Skype Credit for any reason.

Note to uninformed: The described above is based on a promo by Skype effective from early 2006 through the year’s end, enabling calls from internet-connected PC’s physically located in the United States of America or Canada to US/Canadian PSTN and mobiles without purchasing “Skype Credit”.