Really glad you unburdened yourself here. It is so important not to bottle things up, otherwise they fester.
You say you are ashamed to talk about it. Please don't be: having some degree of paruresis is not a judgement of you as a person. As you said, you used to have difficulty in a crowded toilet - not uncommon. Most people can comprehend stage-fright, if only because most people don’t like the idea of standing up and presenting in front of others. Paruresis is a form of stage-fright, but one that is difficult to avoid.
It seems to have really kicked off for you when your confidence took a bump in Mumbai. And from then you have become more self-conscious about peeing. The next day at work, a small set-back had major consequences in starting a chain of self-consciousness.
You mention an office environment: if you drink a lot of coffee, could you stop drinking coffee for a while; it exacerbates anxiety, and triggers a need to pee even when there is a low volume; this makes it more difficult to start a flow.
Then accept that you need to start to use the work toilet at a level you can manage. Use a cubicle (men ARE allowed to pee in a cubicle). If you need to, sit down. Allow yourself plenty of time – can you treat it as a break from work? Continue using the toilet at that level until your equilibrium is restored and you know you can pee that way.
It is important to stop caring whether you pee or not. You cant make it happen: you can only put yourself in a situation that your subconscious is happy with, and then let your body get on with it in its own time. I think of it as walking the dog. I cant make the dog pee, only it will decide whether or not to do so. Meanwhile as a dog walker I think about other things.
Only then consider a move to standing; even then, try it out by faking i.e. go in with no need to pee and do everything except pee – this is so you can feel what it is like at that level. You can repeat the faking until you desense to the new level. Only then introduce peeing at that level. Once you can pee in the cubicle standing up, don’t immediately go to urinals; instead continue standing in the cubicle until one day you realise you went in and peed without thinking about it i.e. it had ceased to be a remarkable event. I would even continue at that level to reinforce that it till it becomes boring. Now moving to an open door or to the urinal can be done using the same procedure of initial faking to check out the new scenario.
As you can see, desense should not be rushed. Small steps, repeated till performance is taken for granted, is what works.
Aside from this, avoid setting yourself a target in time or in performance. Accept what comes along. As for peeing next to someone, accept that a lot of guys like their personal space and so prefer to have a gap either side.
Other guys are not interested in your toileting; to them it is as uninteresting as your blowing your nose.
It would lift a lot of pressure off you to confide in anyone who “needs to know and you trust”. To that end our website has a page called “How to tell someone” It is a low key series of statements that leads the listener along a path they can understand. Based on feedback from hundreds, the reaction will range from understanding to “whatever”. In fact they will quickly forget you told them! Why? Cos it is like you said you have difficulty blowing your nose – hardly memorable. This will mean you not having to pretend anymore.
I hope this is some help. You really can move forward from this.