Yes, you should take him back to the vet.

Though this behavior has been going on for a long time and from a young age, health problems really need to be ruled out. Diet can affect the pH of the urine, making it painful to pee for various reasons. (On the same diet, it may affect some cats and not others, which would explain why his brother is fine). But as otto pointed out, a blood test will not reveal the problem, only a urine sample will. They should be able to express his bladder or use a needle to get a sample.
You need to specifically mention there's a peeing-outside the box problem. He may have some kind of neurological problem. One of our cats pees outside the box when she's in pain (she has dental problems).
Your cat does NOT hate you. Cats don't know that we hate it when they pee outside the box. They can sense the stress it creates - which, if the problem is behavioral, not health related) - makes a circular problem, because they sense your increased frustration, which stresses them further.
But your cat is trying to let you know there's a problem. You just have to work to figure out what it is - and, failing that, how to make him happy and stress free enough to want to use the litter box.

To clean up the places he's peed... have you used specifically an enzyme cleaner? These are the ONLY products that will help to remove the scent of the pee to his sensitive nose, and if he smells urine, it only encourages him to continue to pee outside the box. We use Nok Out (
http://www.nokout.com) and as we had a kitty with a behavioral problem, we went through a LOT of them before we discovered this one.
You must pre-soak any clothing, bedding, whatever with the Nok Out before washing it, and you should add Nok Out to the wash like you would bleach.
For a mattress or carpet or cushions or whatever, you must completely soak the affected area. It's hard with mattresses and sofa cushions, but it really has to be done right to work. (That's why we always order several gallons of Nok Out at a time). Cat pee wicks, so you have to use a lot of the cleaner. You just soak the area... let it sit for 15 minutes, then blot up what you can. For the mattress, we just laid folded towels down over the area, and made the bed - and changed the towels every day before we went to bed.
You should also consider buying a black light. Pee turns up in the black light as an orange splotch, so at night you can go through your home and find all the places you need to treat.
If it's behavioral, you have to do two things (apart from clean up the smell). You have to deny access to where he's been peeing. If it's clothes lying around, pick them up. If it's folded clothes, put them away and don't let him have access to the closets. If it's clean laundry in a basket, don't leave it out anymore.
For the couch, we put strips of aluminum foil over it. If it was because the cushions were soaked with Nok Out, we'd just set throw blankets on it if we wanted to sit on it, and we'd put them away and leave the aluminum foil down when we were done using it.
For carpet, we laid aluminum foil down over the place that had been treated with Nok Out to remind us not to step there until the area dried (it is very important to let it air dry).
For the bed, you can buy a plastic tarp and just throw it over the bed after you're out of it, and fold it up and put it away when you're in it.
I realize he peed on the bed with you in it - but that is just kitty screaming that there is some kind of problem.

You can add more litter boxes. With two cats, you should have three.
You can buy Feliway - either a diffuser (like a plug in air freshener) or the spray. Feliway is a synthetic hormone that mimics the "friendly" markers in cats' cheeks. When cats pee, poop, and scratch, they leave a scent behind that is territory oriented. When they rub their cheeks on something, it is a "happy" thing. Cats are very much about scent, and using feliway can help reduce stress. Just make sure you don't spray it near litter boxes or scratching posts.
There is also a litter that is having huge success. It is called Cat Attract:
Cat Attract certainly does attract the cats!
Is he interested in play? Play can help relieve stress, so if he likes playing, then giving him extra play time often helps.
The most important thing to remember is that your cat is not doing this because he hates you. Something's wrong, that's what he's telling you.
Cats, like little kids, learn better by positive reinforcement. So whenever you do see him using the litter, praise him to high heaven! Maybe give him treats. ...and if you catch him in the act of peeing outside the box, don't say anything, just pick him up and put him in a box and THEN tell him what a good boy he is (if he doesn't just run out and run away). Please don't scold him for peeing outside the box - he doesn't understand why you're upset and it doesn't help him learn just what it is you want.
...but please do get him to the vet first.
