You can actually contact a local printer for that kind of specific printing. You can also shop for general printing online; any offset printer will be happy to find a supplier for you if they cannot print the boxes themselves. They will act as intermediary in that case. They will do any kind of custom box for you.
Another option if you absolutely want to shop online is to have a look at alibaba.com. It's another place where you can find all kind of printers who do high quality box packaging and ship internationally. Most suppliers are in China though but the products (including special boxes and packaging) are very high quality.
There's a lot of choice too and solid boxes as the ones you described; you can have a look at the website and browse the products OR you can select a few suppliers and ask for quotes for custom made packages since you already have your design.
If you decide to choose another style of box for any reason, you can ask them to provide the dieline and use it to have the perfect dimensions of your box for your design. You might need to order your boxes first though.
Note that if what you're looking for is some kind of "drop ship" service (someone who mail your items for you), then you'll probably need to get your boxes printed, and then find a company specialized in distribution.