Thank you for the replies - we upgraded and used the delete commands without any luck. Finally we opened a PMR on the issue. For anyone searching this forum, here is the solution that worked for us;
The smartphone was continuing to try to connect to Traveler which is why the device reappeared in the LotusTraveler.nsf. Apparently the retired employee denied approval to prevent the smarthphone from syncing.
The solution was to add the user to the deny access list in the Domino server document for the Traveler server. This is in the server document on the security tab where we added the user to the 'Not Access Server' list.
Then finally did the user disappear from the LotusTraveler.nsf.
Feedback response number WEBB8YGC38 created by Karen B. Andersen on 09/25/2012