Why isn't Handoff working?

Hey, guys! Hoping someone here can help me. I'm the proud new owner of a retina Macbook (early 2015) and I absolutely love it. I'd like to say that it's been problem free, but I can't- Handoff just isn't working!

I logged into iCloud using the same Apple ID on my iPhone (iPhone 6S, iOS 9.3.3) and when I log into Messages on my Mac, I keep seeing in the left panel under "Preferences" that my account is inactive. Whenever I try to send a message to someone, the name comes up red and I am prompted to sign it- except when I hit the sign in button, I am actually still signed in and the account is enabled! I take a look at iMessage settings on my iPhone and noticed that there is no option for Text Message Forwarding, so it wasn't possible to enable that feature.

I called up Apple Support and they also found it strange that it wasn't working, what they found stranger was that "I had all of the ingredients but it just isn't working"- meaning, I am logged in with the same ID, my number comes up in Message preferences on my Mac, I am signed in with my Apple ID to use iMessage on my iPhone...it's weird. The next day I noticed that some aspects of Handoff were working.

Whenever I opened Safari on my iPhone, it would appear in the Dock on my Mac and vice versa. Same goes for Mail. I also noticed under "phone settings" on my iPhone, that I had the option to answer calls on my iCloud devices, which listed my Macbook. I thought, "great! an improvement!" Later on, I prompted to enter a PIN code by my Mac on my iPhone, and voila! Text message forwarding was there, I entered the code, and then prayed. Back to square-one, Messages on my Mac refused to work. I kept getting the same problem as above. I should note that Safari, Mail and Phone were still working through Handoff.

Today, I noticed nothing was working- no Mail, no Phone and no Safari through Handoff. The option to answer calls on other iCloud devices also disappeared.

When I contacted Apple, I was put with a Senior Adviser...but I haven't heard back yet. He was also stumped by this (but quite helpful). The impression I am getting from Apple is that it's a device-level problem. I am not so convinced, I am thinking it was to do with my account on Apple's end (perhaps server/service level?). To my knowledge, Apple Support and the Specialist haven't looked into that.

Here's what I tried:

1. Turning iMessage/Facetime on my iPhone on and off.
2. Signing out my Apple ID for iMessage and Facetime and then signing back in.
3. Signing out and signing back in on Messages and Facetime on my mac.
4. Signing in and out of iCloud on my iPhone and Mac.
5. Restarting both devices while disconnected from the internet.
6. Tried signing in using App password. (didn't work)
7. Turned off two-step verification. (it's on again)
8. Signing in on all of my Apple ID account using only my iCloud domain email.
9. Restored iPhone as new.
10. Internet recovery on Macbook.
11. Checked that my iPhone sets timezone automatically.
12. Ensured that iMessage/Facetime region and iPhone/Mac region were the same (United States)

    I should note that the region of my Apple ID is set to Barbados (where I'm from) so that I can use my local credit card for App/iTunes Store purchases- but I don't see how or even why that would affect Handoff

13. At the request of the Senior Adviser, I called my wireless provider (Flow Barbados) to figure out if they support Text Message Forwarding (they had not idea what I was talking about, at first they said no figuring it was like call forwarding and then when I explained to them, they said they weren't sure and to get in touch with Apple again).
14. I'm not sure if this has anything to do with it, but I find my iPhone refuses to connect to my MacBook via bluetooth after pairing, my MacBook would say connected and my iPhone would say not connected, and the eventually it would fail. But sometimes, it does work when I am using Handoff apps...weird. Also, I can't seem to get AirDrop to work, my devices don't detect each other. Just said I'll mention this in case it helps.

Honestly, this has been plaguing me for a few days now and I am truly at a loss as to what I should do.

Any ideas or suggestions? Anything would be appreciated.

UPDATE: Handoff for Phone, Mail and Safari is working again...still no luck with Messages.