Are isomorphic structures really indistinguishable?

It depends on the structure you are talking about. Isomorphisms are defined to respect a given structure - for example in the category of sets the isomorphisms are just bijections. Any two sets with a bijection between them are virtually indistinguishable - the elements are just labelled differently. However, in the category of groups, the isomorphisms respect the group structure, so given two isomorphic groups they are indistinguishable as groups - i.e. if I multiply two elements in one group, the answer is the corresponding multiplication in the isomorphic group.

Basically isomorphisms will preserve the structure that is inherent in the maps you define between objects in a given category. If you want your maps to preserve a certain property, you define them that way.

For an example, if you consider metric spaces, you can consider only (continuous) functions between then which preserve distances, or those that do not have to. The notion of isomorphism is different in both cases.

You should learn some category theory. It provides some elegant language for discussing the issues you're running into.

In fact there are groups that are isomorphic (wrt group isomorphisms) but have different properties, for example, when seen as permutation groups.

As I said above, if you want to talk about properties of permutation groups which are not captured as properties of groups, then you don't want to talk about isomorphism of groups but isomorphism of permutation groups. More precisely, we can define the category $\text{GrpAct}$ of group actions and talk about isomorphism in this category. This is the category whose objects are triples $(G, X, \rho)$ where $G$ is a group, $X$ is a set, and $\rho : G \to \text{Aut}(X)$ an action of $G$ on $X$; and whose morphisms $(G_1, X_1, \rho_1) \to (G_2, X_2, \rho_2)$ are pairs $(\phi, f)$ where $\phi : G_1 \to G_2$ is a homomorphism and $f : X_1 \to X_2$ is a set map satisfying $$\rho_1(g)(x) = \rho_2(\phi(g))(f(x))$$

for all $g \in G_1, x \in X_1$. Isomorphism in this category captures isomorphism of permutation groups (the special case where $\rho$ is injective), which is a stronger condition than isomorphism of abstract groups. More precisely, there is a forgetful functor

$$F : \text{GrpAct} \to \text{Grp}$$

sending a group action $(G, X, \rho)$ to the group $G$, and the basic phenomenon you are observing is that two objects $a, b \in \text{GrpAct}$ may not be isomorphic even if $F(a)$ and $F(b)$ are. This is not surprising and is in some sense typical.

Analogously (and surprisingly!), even if we say that G is a group and G∗ is a permutation group, we are talking about different mathematical object, even if they are isomorphic as groups!

From the perspective of category theory, the problem is that groups and permutation groups live in different categories. To compare them, you need to use the forgetful functor $F$, and then you need to distinguish between a permutation group (which lives in $\text{GrpAct}$) and the corresponding abstract group (which lives in $\text{Grp}$) as mathematical objects.

To use a computer science analogy (well, more than an analogy, but...), the forgetful functor typecasts between the types GroupAction and Group, and the isEqual operator is defined differently for the two types (and does not compare a GroupAction and a Group; you need to typecast first).

As Paul and Jyrki wrote, isomorphism preserves a structure. Not all possible structures.

If we only consider sets (without structure) then isomorphism is simply a bijection. In this sense $\mathbb N$ and $\mathbb Z$ are indeed isomorphic, since both are countable. If we now want an order isomorphism, then $(\mathbb N,<)$ and $(\mathbb Z,<)$ are no longer isomorphic (assuming that $<$ is the natural order, that is).

Another relatively simple example: consider the fields $\mathbb Q$ and $\mathbb Q(\pi)$. As ordered sets these are isomorphic, every countable, dense linear order without endpoints is isomorphic to $\mathbb Q$. However if you now want the isomorphism to respect the field operations then we cannot find such isomorphism since one of them contains a transcendental element and the other does not.

This is why when talking about isomorphism it should be specified what structure we preserve, or it may be clear from context.

I'm not sure, if this is what you are referring to, but here goes...

There are questions that are easy to decide in one structure, but much more difficult in another isomorphic structure. The discrete logarithm problem comes to mind. The additive group $G_1=\mathbf{Z}_{502}$ is generated by $5$, and to a given $x\in G_1$ finding a multiplier $n$ such that $$ 5n=(5+5+\cdots 5)=x $$ is easy, as the generalized Euclidean algorithm will do it for us.

The multiplicative group $G_2=\mathbf{Z}_{503}^*$ is also cyclic of order $502$ and also generated by $5$. Yet, to a given $x\in G_2$ the problem of finding an exponent (now an exponent as the group is multiplicative) $n$ such that $$ 5^n=(5\cdot5\cdot5\cdots5)=x $$ is more difficult. The difference in difficulty becomes more pronounced as the size of the groups grows.

The problem is that describing an isomorphism is not enough to translate a question from one structure to the other, if you cannot also describe its inverse.