I want to discuss bold links, I mean links that reside inside <h1>..<h6>, <b>, <strong> and stuff. Does G (and/or any other SE) really rank them a bit higher than plain <a>? If it does then how it is correct to place tags? I know about <Hx> is a block element, so it cannot be placed inside <A> which is inline. But what about <b> and <strong> which are also inline?

Assumption #1:
<a href="someurl"><b>Some Word</b></a>
Some Word is logically outlined

Assumption #2:
<b><a href="someurl">Some Word</a></b>
The whole link is logically outlined

Which one is correct? I suppose that #2 is, because it looks more similar to <h1><a href="lalala">Lalala</a></h1>, but I still have doubt.

1/ or 2/ would be correct to HTML standards and for SEs either, neither or both.

it makes no difference to SEs. as <b> <hn> <strong> <em> etc make no difference when taken as individual items for SE ranking. It's the whole combination of correctly structured documents and elements used in the correct context that works best.

OK, now lets assume that a have some not-totally-random text. I want to logically outline some words within, I want to make some words to be a link and I want some words to be bold link for higher relevance. I don't try to fool a SE spider by placing bold links randomly (you may see an example of how it works here). So what is better in this case: <a> between <b>..</b> or <b> between <a>..</a>?

As I said previously neither.
Anchor text is already given more weight than standard text for the target page. making anchor text bold isn't going to give it more relevance. However bolding words is a good way of making them stand out to real visitors. You know the ones with credit cards

Stop thinking what formula is currently deemed to be best for search engines, because it will have changed by the time to have finished updating your site and you then have to start again with a new formula, because "<h4> is the new bold" to paraphrase the fashion trade.
There is more theories and mis-information around the latest and greatest "formula" for top rankings and each one contradicts the other. The simple fact is nobody actually knows, what works on one site is very likely to bomb out on another. It's something that makes this kind of job interesting, and the skill is in knowing how to apply the various elements in the ideal way for it to work.

Do what is best for site visitors and funnily enough the search engines like it too, That's all SEs not just the one.

Do what is best for site visitors and funnily enough the search engines like it too, That's all SEs not just the one.

Totally in agreement with this. create a site for your users and SE will love it.