Trouble eluting all protein from avidin beads - (Feb/24/2015 )

I'm working with Neutravidin agarose beads (deglycosylated avidin), pulling down a biotinylated molecule and using SDS-PAGE sample buffer and 10 minutes' boiling to elute the protein. Although the protein does elute, when I run the beads on a gel, I see a fair amount of my protein still bound to the beads. It's especially concerning because the fraction left on the beads is uneven (on my last experiment, it varied from about 10% to 35% still bound). Other than increasing the sample buffer concentration and/or increasing the boiling time (I will try these things), can anyone suggest another elution buffer that is compatible with SDS PAGE gel downstream?

Can you use Urea? But if you use urea, you should not boil sample. Just add SDS dye and load on PAGE.