When asking questions about Gremlin it is helpful to include some sample data in the form of a Gremlin script (and in the case of DataStax Graph perhaps a schema script as well).

g.addV('Person').as('p').
  addV('Department').property('name','dept1').as('d1').
  addV('Department').property('name','dept2').as('d2').
  addV('Department').property('name','dept3').as('d3').
  addV('Address').property('name','addy1').as('a1').
  addV('Address').property('name','addy2').as('a2').
  addV('Address').property('name','addy3').as('a3').
  addE('EmployeeOf').from('p').to('d1').
  addE('EmployeeOf').from('p').to('d2').
  addE('EmployeeOf').from('p').to('d3').
  addE('LivesAt').from('p').to('a1').
  addE('LivesAt').from('p').to('a2').
  addE('LivesAt').from('p').to('a3').iterate()

Note that in this case, I simplified a bit since the regex and person "name" didn't have much bearing on your traversal question.

Is it the right way to do more traversals on one vertex? Is this approach we are doing allowed/ok?

I think you have a fair bit of unnecessary complexity in your traversal. That complexity hurts performance and makes the query difficult to read. In particular, there is a heavy use of step labelling (i.e. use of "as()") which enables path tracking in your traversal and adds to computation cost. If you can avoid path tracking you will increase your performance. The use of "otherV()" has similar effect and in this case it is not necessary as you've traversed with "outE()" so the alternate side is known and must be "inV()". Typically, "otherV()" is reserved for use in conjunction with `bothE()` where the traversal direction is not known.

Removing all that complexity and considering what you expect as a result should reduce your traversal to something as simple as:

g.V().has('Person','names',regex('.*') ).
  union(out('EmployeeOf').limit(2),
        out('LivesAt').limit(2))

Using my example data you can see that I get the result you're looking for:

gremlin> g.V().hasLabel('Person').
......1>   union(out('EmployeeOf').limit(2),
......2>         out('LivesAt').limit(2)).
......3>   project('name','label').by('name').by(label)
==>[name:dept1,label:Department]
==>[name:dept2,label:Department]
==>[name:addy1,label:Address]
==>[name:addy2,label:Address]

Why do we get two different addresses but only one unique department, but this is added twice to the result? How to solve this?

While you can see the solution above, it's worth understanding why you were getting the result you were getting. I think Bettina's answer explains it but, said another way, keep in mind that "range()" is a filter not a barrier. In other words, it does not exhaust the stream of traversers up to it. So, your first "range()" yields one "department" traverser which flows through to "outE('LivesAt')" and triggers a "LivesAt" edge to flow toward the second "range()". Then, the next available "LivesAt" edge flows through the second "range" but that is the limit. Those two traversers flow to "union()" and they each get to do a "select()" and thus produce four results. That means two unique addresses (one for each "LivesAt") but then the same "department" because that was traverser to originall trigger the rest of this stream. As we've reached the limit of the second "range()", this traversal is considered done. So the second "range()` interferes with the first.

If my solution above is not good for your particular environment you might consider some variation of it. The pattern for avoiding the "range()" interference I just described is to explicitly use "range()" inside of the "union()" or more generally within sub-traversal which can be individually iterated to completion.