You bet they can!!
The organizers of the Manitoba Randonneurs, who have been involved in Randonneuring for probably about 25 years now, have been riding a tandem for about half that time .... including several PBPs.
Just about any human powered machine is allowed.
They do start at a different time on the PBP, but for any other brevet they start and ride with all the other riders.
It was great when I rode in Manitoba ... there were often two tandems out there, and we'd all ride in a long paceline for the first 75 kms or so. The couple I mentioned above are VERY strong riders ... then they'd put the slowest riders right behind them (usually me and one other girl), then the other tandem, and then the rest of the guys ...... and we'd fly!! After about 75 kms though, the strong tandem couple would want to pick up the pace, and so they'd disappear in the distance but the rest of us would try to stay with the slower tandem couple. Lots of fun!