Q:

Detecting if two images are similar

Could someone give me a push in the right direction, if I am willing to determine if
two images actually make a panorama together (or are panorama-like, e.g contain "same" parts, which are obviously a bit transformed).

A:

The technique you are after is known as "image stitching". There is a reasonable Wikipedia entry on it. That gives a few hints about how the algorithm would work.
It's necessarily a tricky heuristic. You need to find groups of pixels that are similar (but obviously not identical). This could include parts that are rotated slightly, scaled slightly, or coloured slightly differently.

A:

There are several articles on stitching images together:

Implementation of HDR panorama stitching algorithm
Image Alignment and Stitching: A Tutorial
http://www.codeproject.com/KB/recipes/automatic_panoramas.aspx

The last one is a good tutorial that uses the LGPL library Accord.NET.

