The problem is that the default Message shapes inside UML Sequence stencil have a special User-defined value that transforms them to Return messages if they go from right to left.
An elegant solution is to right click on the "UML Sequence" stencil and select Save As. Name it something like "UML Sequence Fixed". Open the newly created stencil. Go to File->Options->Advanced->General and check Run in developer mode.
Now right click on the Message shape and select Edit Master->Edit Master Shape (you might need to right click on the stencil title in the list and select Edit Stencil. Now click on the arrow image that opened in the new split to select it. In the ribbon go to the Developer menu click on Show ShapeSheet->Shape there in User-defined Cells you will find a property called User.IsReturn (its value is EndX<BeginX). Change that to 0. Close the opened splits (visio will ask you whether to save the shape and you should choose yes).
Now do the same operation for Asynchronous Message and Return Message (except choose 1 for the value in the case of the Return Message).
With your new stencil you will be able to create both left-to-right and right-to-left messages.