I think the reason why parallax mapping looks strange and cause weird things is because it's hard, really hard, to actually make it match the perceived elevation changes from the normal map in both location and elevation.
Using the height map from which the normal map was created is a bad idea because the normal map cannot be used to add rectangular surface geometry changes, it's all angled... so basically you can get a gradual change in elevation when you look at the normal map, but an immediate change when you look at the parallax effect from the height map. Additionally, the amount of parallax shift is difficult to match exactly to the elevation change that is perceived by the width and the angle of the changes on the normalmap.
or in images, if the original height map has sharp transitions like this:

The normal map generated from this will look something like this (depending on the filter used, this uses 3x3 filter):

So profile-wise, the original height map in this case looks something like this:

...while the normal map's profile looks more like this:

Ideally, the parallax map would need to be re-created from the normal map in order to avoid the profile changes, and I don't really have any tools that can do that properly; GIMP's normal map plugin does have a convert to height option, but it doesn't work very well and adds a silly gradient to the images like this:

so I'm sure you can see what that would do to things like tiling and general accuracy of the parallax map.

nvDXT interestingly has -toHeight flag in the instructions, but using it jsut tells that it's an unknown option, so go figure.

Anyway, even if I could convert the normalmap back to an accurate heightmap profile-wise, that doesn't really answer to the problem of scaling the normal map and parallax map to match each other's elevation (or perceived elevation), which can cause weird things when some areas' parallax seems to be more, or less, than what the normalmaps apparent elevation difference would suggest. That's likely the reason why normal maps tend to work better alone than with the parallax maps, at least on ships. I don't really know how it would be possible to truly match the two different maps into one seamless effect.