B&C Honey Farm http://www.flickr.com/photos/9848229@N05/
Do what works for you, I do what works for me And in all sincerity....I couldn't imagine having 1000's of boxes and maybe my opinion would change...who knows...I can only comment on what I know.
We brand our boxes too and we have thousands of them. Not on all four sides and not the lids. I consider paint almost a waste of time, a couple guys with a spray can would be able to make your boxes his very quickly. As others have said, it might keep the honest guy honest.
I think one of the ways people get ripped off in California is for the thieving beek to go in with his boxes and strip your colonies of the middle 5 frames, no amount of branding is going to stop him and it is hard to check the frames if they are branded.
With all the selling of used equipment amongst beekeepers over the years, having someone else's brand on your boxes and frames in and of itself doesn't raise any red flags. The fact of the matter is you take a chance taking your bees anywhere out of your sight, more so as the prices of honey and pollination fees rise. A secure location is your best protection.
If you do have bees stolen and you are able to locate them, ( actually not as uncommon as you might think ) the sheriff will almost certainly require you to provide some form of verifiable ID between you and yours before he will release them to your possession. It helps if the ID is in a form the deputy can recognize, such as DL no., name & address, etc. It may take a little time before they recognize a state apiary ID#. When you want to get your hands on your property and move it, this is important.
I use a propane branding iron. You can do a lot of boxes and frames in a hurry and it smells better than paint or magic marker.